非円形性スコアをプログラムする

あなたの仕事は、2D平面内のポイントの空ではない有限集合 A をとり、非円周スコア
s(A)を出力する数学関数 s は次のプロパティを満たします:

  1. Positive Definiteness: If there is a circle or a
    straight line that contains all points of A, then
    s(A) = 0. Otherwise s(A) > 0
  2. Surjectivity: It is surjective to the nonnegative real
    numbers, that means for every nonnegative real number
    r there is a finite subset A of the plane
    such that s(A) = r.

  3. Translation Invariance: s is translation
    invariant if s(A) = s(A + v) for every vector
    v and for all A.

  4. Scale Invariance: s is scale invariant, if
    s(A) = s(A * t) for every t≠0 and for all
    A.

  5. Continuity. s is said to be
    continuous if the function f(p) := s(A ∪ {p})
    (mapping the a point p to a real number) is continuous
    using the standard absolute value on the real numbers, and the
    standard euclidean norm on the points of the plane.

直感的に言えば、この非円形度スコアは、線形回帰の相関係数と同様のものと考えることができます。

詳細

理論上の関数は実数で動作しなければなりませんが、この挑戦​​の目的のために浮動小数点数を代用として使用することができます。提出の説明と、これらの5つの財産がなぜ保持されるのかの議論を提供してください。
2つの座標のリスト、タプルのリスト、または入力と同様のフォーマットを取ることができます。入力のポイントが繰り返されない、つまりすべてのポイントが一意であると仮定できます。

ベストアンサー

Python、124バイト

lambda A:sum(r.imag**2/2**abs(r)for a in A for b in A for c in A for d in A if a!=d!=b!=c for r in[(a-c)*(b-d)/(a-d)/(b-c)])

複素数のシーケンス( x + 1j * y )として A をとり、Im(
r2 A の4点のすべての複雑な交差比 r に対して、>/2
| r |

プロパティ

  1. Positive Definiteness. All terms are nonnegative, and
    they’re all zero exactly when all the cross-ratios are real, which
    happens when the points are collinear or concyclic.

  2. Surjectivity. Since the sum can be made arbitrarily
    large by adding many points, surjectivity will follow from
    continuity.

  3. Translation Invariance. The cross-ratio is
    translation-invariant.

  4. Scale Invariance. The cross-ratio is scale-invariant.
    (In fact, it’s invariant under all Möbius transformations.)

  5. Continuity. The cross-ratio is a continuous map to the
    extended complex plane, and r
    Im(r)2/2|r| (with ∞ ↦ 0) is
    a continuous map from the extended complex plane to the reals.

(Note: A theoretically prettier map with the same プロパティ is
r ↦ (Im(r)/(C +
|r|2))2, whose contour lines w.r.t.
all four points of the cross-ratio are circular. If you actually
need an uncircularness measure, you probably want that one.)

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です