1
\$\begingroup\$

The Sylvester-Gallai theorem says: Suppose you have a finite list of points in the plane. Suppose further that not all of those points are collinear (lie in a single line). Then there is some line containing precisely two of the points. (That is, there's some line on which two of the points lie, but not more than two.)

You task is to find such a line. Note that more than one exists; you need to find one.

Input:

A bunch of points denoted by their Cartesian coordinates. You may assume the coordinates are nonnegative integers, if you like. The string (1,2),(0,4),(5,6) and the list 1, 2, 0, 4, 5, 6 and other formats are fine, and can be function parameters or read from STDIN or whatever.

If you prefer, allow also radical-root input (with positive-integer index). Then, each point will be represented by four numbers: the index and radicand of the abscissa, and the index and radicand of the ordinate. A rational number will be represented with index 1. Again, the input can be like ((1,2),(3,4)),((6,7),(8,9)),((2,3),(4,5)) or like 1, 2, 3, 4, 6, 7, 8, 9, 2, 3, 4, 5, or what-have-you. You may assume that the radicand is a nonnegative integer.

You may assume the points are distinct from one another and are not all collinear (and thus, in particular, that there are more than two points).

Output:

A line guaranteed by Sylvester-Gallai. This can be presented in any Cartesian-based form that completely specifies the line and allows people to visualize it. (I expect that answers will typically use either the line's slope and a point on it or two points on the line.)

Scoring:

This is a popularity contest. The answer with the greatest number of net votes after about a week will get the checkmark. Everyone can vote at will, obviously, but I, personally, will bear in mind at least these factors: ingenuity of the solution (including avoidance of the brute-force method), explanation of the code, ability to accept radical-root input, and simplicity of the code (in flop count / runtime).

\$\endgroup\$
  • 7
    \$\begingroup\$ Why a pop con for such a specific task? Having specific criteria as a voting guide is good, but I don't imagine there being much room for ingenuity for solutions. \$\endgroup\$ – xnor Jan 17 '16 at 10:28
  • \$\begingroup\$ @xnor, afaik there's no nice algorithm for generating such a line. So someone's gonna have to come up with something. If it's the obvious brute force, so be it. If it's not, well, that's better. \$\endgroup\$ – msh210 Jan 17 '16 at 10:32
  • \$\begingroup\$ @msh2010 Yes, I was thinking the obvious brute force. You don't mention run-time as a criterion, and it's quite simple. If you don't want that, you should say so. \$\endgroup\$ – xnor Jan 17 '16 at 10:34
  • 2
    \$\begingroup\$ I find it weird to put not brute-forcing under ingenuity, since without giving a reason the brute force is bad, it feels like asking for creativity for the sake of creativity, which is broad. Regardless, beware that popularity contests are really disfavored by site culture now and have always been a grey area in the site rules for objectivity, so your question has a good chance of getting closed just as a pop-con. Someone should have mentioned this in the sanbox... \$\endgroup\$ – xnor Jan 17 '16 at 10:45
  • 3
    \$\begingroup\$ "afaik there's no nice algorithm for generating such a line" puzzles me, because you link to a Wikipedia page which links to a O(n lg n) algorithm. \$\endgroup\$ – Peter Taylor Jan 17 '16 at 17:12
4
\$\begingroup\$

Python 2, not golfed

Sure, they say there's a worst case O(n*log(n)) algorithm, but who cares about the worst case? It's the average case we usually care about, and this simple random algorithm runs in expected linear time on arbitrary inputs!

(By comparison, the deterministic brute force algorithm can be fed carefully constructed inputs to force it to run in quadratic time at least.)

import random,math
def radical_to_normal(x,y): return (x[1]**(1./x[0]),y[1]**(1./y[0]))

def distance_to_line(p1,p2,p3): 
 dx = p2[0] - p1[0]
 dy = p2[1] - p1[1]
 return abs(dy*p3[0] + dx*p3[1] + p2[0]*p1[1] - p2[1]*p1[0]) / math.sqrt(dy*dy + dx*dx)

points = input() #input as list of pairs
c = True
while c:
    c = False
    p1,p2 = random.sample(set(points), 2)
    for p3 in points:
        if distance_to_line(radical_to_normal(*p1), radical_to_normal(*p2), radical_to_normal(*p3)) < 0.00001:
            c = True
print p1,p2

Example run:

➤ python sylvester.py
[((1,0),(1,0)),((1,1),(1,0)),((1,2),(1,0)),((1,0),(1,1)),((1,1),(1,1)),((1,2),(1,1)),((1,0),(1,2)),((1,1),(1,2)),((1,2),(1,2))]
((1, 2), (1, 2)) ((1, 0), (1, 1))

How it works

It's been proved (Csima and Sawyer 1993) that roughly 6/13 of all lines in any set are ordinary (only involve 2 points from the set) except when n=7. As the number of points goes to infinity, the lower bound goes to 1/2 of the lines (Green and Tao 2013). Therefore, we expect to have to test around 2-3 pairs of points on average before finding an ordinary line if we sample pairs of points at random.

This simple program just selects a random pair of points, then checks the distance from the line they form to a third point, which ranges over all points in the set. All three points are converted from radical root form to floats by radical_to_normal() before the distance is calculated by distance_to_line(). If the distance is below a threshold (indicating they are collinear), we set a sentinel to try again. Until every point tested passes above the threshold, we try, try again. (This threshold could be made much smaller and still work, of course.)

Since we test an expected constant number of point pairs, and we test n points for each pair, the algorithm runs in expected time O(n).

\$\endgroup\$
  • \$\begingroup\$ I must not have been very good at Python when I wrote this, because it is stupid to use a sentinel on a while loop here. A cleaner, faster solution would be to use while True:, put a break in the inner loop condition, and another break in an else clause on the for loop to leave the while loop cleanly. Python learners take note. \$\endgroup\$ – quintopia Oct 6 '17 at 19:28
0
\$\begingroup\$

Mathematica, 73 bytes

Cases[#~Subsets~{2},p_/;InfiniteLine@p~RegionMember~#~Count~True==2,1,1]&

Test Case:

%[{{0,0},{1,1},{3,2},{3,3},{6,4},{4,5}}]
(* {{{0,0},{4,5}}} *)

Explanations:

#~Subsets~{2} gives all pairs of points; InfiniteLine@p~RegionMember~#~Count~True==2 tests whether there are exactly two points intersect the infinite line given by a pair of points p; Cases[..., ..., 1, 1] gives the first pair of points that meet the condition.

Mathematica naturally accepts numbers like 3/5, Pi, Sqrt[2], etc, and gives accurate results as long as the inputs are accurate.

\$\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.