Circles through two points that always enclose many points Journal Article


Author(s): Edelsbrunner, Herbert; Hasan, Nany; Seidel, Raimund; Shen, Xiao-Jun
Article Title: Circles through two points that always enclose many points
Affiliation
Abstract: 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.
Journal Title: Geometriae Dedicata
Volume: 32
Issue 1
ISSN: 0046-5755
Publisher: Kluwer  
Date Published: 1989-10-01
Start Page: 1
End Page: 12
DOI: 10.1007/BF00181432
Notes: Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by the National Science Foundation under Grant CCR-8714565, by the second author has been partially supported by the Digital Equipment Corporation, by the fourth author has been partially supported by the Office of Naval Research under Grant N00014-86K-0416.
Open access: no
IST Austria Authors
Related IST Austria Work