3 ms·
> According to a strengthening of the theorem, every finite point set (not all on one line) has at least a linear number of ordinary lines. An algorithm can fin
by pratikdeoghare 2mo ago
> According to a strengthening of the theorem, every finite point set (not all on one line) has at least a linear number of ordinary lines. An algorithm can find an ordinary line in a set of n points in time O(n log n). [1]
There are many such lines (think convex hull) and they are easy to find.
This makes it hard to appreciate the theorem.
You keep thinking oh whats the big deal.
[1] https://en.wikipedia.org/wiki/Sylvester%E2%80%93Gallai_theorem https://en.wikipedia.org/wiki/Sylvester%E2%80%93Gallai_theor...
- tirutiru 2mo agoThe boundary lines of the convex hull can easily have 3 points each. So not as obvious as all that.