Circles through two points that always enclose many points
This paper proves that any set of n points in the plane contains two points such that any circle through those two points encloses at least n12−112+O(1)n47 points of the set. The main ingredients used in the proof of this result are edge counting formulas for k-order Voronoi diagrams and a lower bound on the minimum number of semispaces of size at most k.
32
1
1 - 12
1 - 12
Kluwer