Find the line guaranteed by Sylvester-Gallai

Question

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

Answer 1

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

Answer 2

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.