1
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).
8Why 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. – xnor – 2016-01-17T10:28:30.903
@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. – msh210 – 2016-01-17T10:32:11.023
@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. – xnor – 2016-01-17T10:34:53.790
@xnor, better now, you think? – msh210 – 2016-01-17T10:40:38.403
2I 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... – xnor – 2016-01-17T10:45:30.233
@xnor, probably shoulda, yeah... well, we'll see what happens. – msh210 – 2016-01-17T13:52:56.167
Can we assume, when you say "all points are distinct from one another" that "all points are at least x distance from one another for some threshold x"? This would help with doing floating point arithmetic. – quintopia – 2016-01-17T16:54:40.630
@quintopia, "You may assume the coordinates are nonnegative integers, if you like" – Peter Taylor – 2016-01-17T17:09:55.000
@PeterTaylor But what if you don't like? For instance if you want to do the radical roots version? – quintopia – 2016-01-17T17:11:08.973
4"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. – Peter Taylor – 2016-01-17T17:12:30.163
@quintopia, even in the radical-roots version you can assume the radicands are integers. But yeah I suppose you can assume the points are some distance apart. – msh210 – 2016-01-17T18:51:59.597
@PeterTaylor, right, when I wrote that comment I forgot that. – msh210 – 2016-01-17T18:59:20.323