16
\$\begingroup\$

Your task is to program a mathematical function s, that takes a nonempty finite set A of points in the 2D plane, and outputs an uncircularity score s(A) that satisfies following properties:

  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.

Intuitively speaking this uncircularness score can be thought of as something similar to the correlation coefficient in linear regression.

Details

Your function in theory has to work in the reals, but for the purpose of this challenge you can use floating point numbers as substitute. Please provide an explanation of your submission and an argument why those five properties hold. You can take two lists of coordinates or a list of tuples or similar formats as input. You can assume that no point in the input is repeated i.e. all points are unique.

\$\endgroup\$
  • 1
    \$\begingroup\$ Could you add a few test cases? \$\endgroup\$ – Shaggy Dec 22 '17 at 0:39
  • \$\begingroup\$ What does it mean for a circle to contain all points of A? \$\endgroup\$ – H.PWiz Dec 22 '17 at 2:05
  • \$\begingroup\$ @H.PWiz Consider a circle as a subset of the 2d plane, the a point is contained in the circle if it is an element of this subset. \$\endgroup\$ – flawr Dec 22 '17 at 9:20
  • \$\begingroup\$ @Shaggy No that is not possible since s is not unique. The only thing you could make examples for is for s(A) = 0 which is trivial to do using the first property. \$\endgroup\$ – flawr Dec 22 '17 at 9:41
  • \$\begingroup\$ Can our program error out in theorically zero probability? (the actual probability is nonzero because floating point number is discrete) / Do you allow floating point imprecision to be ignored? Relevant meta. \$\endgroup\$ – user202729 Dec 22 '17 at 11:51
2
\$\begingroup\$

Python 2 with numpy, 116 bytes

from numpy import*
def f(x,y):a=linalg.lstsq(hstack((x,y,ones_like(x))),(x*x+y*y)/2);return a[1]/sum((x-a[0][0])**4)

Takes x and y as 2d column vectors and returns an array containing the answer. Note that this will give an empty array for a perfectly straight line or with 3 or fewer points. I think lstsq gives no residuals if there's a perfect fit.

Explanation

Essentially, this finds the circle of best fit and gets the squared residuals.

We want to minimize (x - x_center)^2 + (y - y_center)^2 - R^2. It looks nasty and nonlinear, but we can rewrite that as x_center(-2x) + y_center(-2y) + stuff = x^2 + y^2, where the stuff is still nasty and nonlinear in terms of x_center, y_center, and R, but we don't need to care about it. So we can just solve [-2x -2y 1][x_center, y_center, stuff]^T = [x^2 + y^2].

We could then back out R if we really wanted, but that doesn't help us much here. Thankfully, the lstsq function can give us the residuals, which satisfies most of the conditions. Subtracting the center and scaling by (R^2)^2 = R^4 ~ x^4 gives us translational and scale invariance.

  1. This is positive definite because the squared residuals are nonnegative, and we're dividing by a square. It tends toward 0 for circles and lines because we're fitting a circle.
  2. I'm fairly sure it's not surjective, but I can't get a good bound. If there is an upper bound, we can map [0, bound) to the nonnegative reals (for example, with 1 / (bound - answer) - 1 / bound) for a few more bytes.
  3. We subtract out the center, so it's translationally invariant.
  4. We divide by x**4, which removes the scale dependence.
  5. It's composed of continuous functions, so it's continuous.
\$\endgroup\$
  • \$\begingroup\$ Can you elaborate what your submision is actually computing? \$\endgroup\$ – flawr Dec 22 '17 at 18:49
  • \$\begingroup\$ @flawr Edited that in. \$\endgroup\$ – Mnemonic Dec 22 '17 at 19:47
  • \$\begingroup\$ I tried to test this on {(1, 0), (2, 0), (3, 0), (4, t)} for t → 0, but f(array([[1.0],[2.0],[3.0],[4.0]]),array([[0.0],[0.0],[0.0],[t]])) seems to give me array([ 0.00925926]) for all nonzero t. (I know you said this breaks for t = 0, but the result should at least approach 0 for t → 0.) Am I calling it wrong? \$\endgroup\$ – Anders Kaseorg Dec 24 '17 at 4:42
2
\$\begingroup\$

Python, 124 bytes

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)])

Takes A as a sequence of complex numbers (x + 1j*y), and sums Im(r)2/2|r| for all complex cross-ratios r of four points in A.

Properties

  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 properties 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.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.