GTX0 NewestRepliesHottestMy Active
NIFE UpdatesRoadmapRequests | HelpDiscuss Game Worlds

Points and Lines
Posted: Posted November 6th, 2017
Edited November 6th, 2017 by The Fly

Take any \(N\) points in the plane (at least 3) and suppose they aren't all on the same line (i.e., they're not colinear). Then the conclusion is that there will always be two points among them that lie in a line that never goes thru any of the other remaining points.

For \(N = 4, 5, 6\) points its easy to reason out. For more it becomes bit more delicate (but not very hard).

This is called the Sylvester-Gallai Theorem and it's a neat result in projective geometry that uses logic and pigeonhole type arguments.

Hope you like it. Have fun.
The Fly


There are 7 Replies

I found a general solution that proves this for all n. I'll post it after I make some pictures (they're pretty necessary)

Posted November 7th, 2017 by Xhin
Nature is beautiful

Actually I found an even more elegant solution while trying to organize my notes. This one might not require pictures.

For any scattering of n points where they're not all on the same line, you will have an overall "shape" of the outer boundary. This can be a triangle, a quadrilateral, etc. Let's call the number of sides of that shape d.

If you make lines to make whatever that shape is, then you have found solutions. There may be some points inside those shape lines that make that particular solution fail. Let's call the number of those points s.

So then, for any d-sided shape whatsoever, no matter what the points look like inside there will always be at least d-s solutions.

What if d = s? Well in that case you can form a new shape of the same number of sides where all the s points form the outer boundary. Then you apply the same exact rules to this shape.

Whatever your boundary shape is will infinitely recurse as you try to break all the old solutions, inscribing the same n-gon in itself over and over.

Posted November 7th, 2017 by Xhin
Nature is beautiful

Glad you find it interesting Xhin. The shape you are describing is called the convex hull of the points. It is the smallest convex set containing all the points. The boundary of that set will consist, as you alluded, of a number of line segments. Each of these could however contain 3 points or more. How does one get a single line that contains two and only two points from the initial set?

Posted November 7th, 2017 by The Fly

What about the Fano plane?

Edited November 8th, 2017 by EN

The line joining 1 and 2 contains none of the other points. (Also 2 and 4, or 1 and 4.)

Posted November 9th, 2017 by The Fly

The part that looks like a circle is actually a line that contains 1, 2, and 4. From the wiki page:

In finite geometry, the Fano plane (after Gino Fano) is the finite projective plane of order 2, having the smallest possible number of points and lines, 7 each, with 3 points on every line and 3 lines through every point.

Posted November 9th, 2017 by EN

Yes, but the Sylvester-Gallai Theorem is for the usual Euclidean plane with the usual straight lines. (Not for all projective spaces).

Posted November 10th, 2017 by The Fly
Site Rules | Complaints Process | Give Feedback Facebook Page
GTX0 © 2009-2019 Xhin GameTalk © 1999-2008 lives on