🔖 Sylvester‚ÄďGallai theorem | Wikipedia

Bookmarked Sylvester‚ÄďGallai theorem (Wikipedia)

The Sylvester‚ÄďGallai theorem in geometry states that, given a finite number of points in the Euclidean plane, either
* all the points lie on a single line; or
* there is a line which contains exactly two of the points.
It is named after James Joseph Sylvester, who posed it as a problem in 1893, and Tibor Gallai, who published one of the first proofs of this theorem in 1944.

A line that contains exactly two of a set of points is known as an ordinary line. According to a strengthening of the theorem, every finite point set (not all on a line) has at least a linear number of ordinary lines. There is an algorithm that finds an ordinary line in a set of n points in time proportional to n log n in the worst case.

Leave a Reply

Your email address will not be published. Required fields are marked *