Circles through two points that always enclose many points
Edelsbrunner H, Hasan N, Seidel R, Shen X. 1989. Circles through two points that always enclose many points. Geometriae Dedicata. 32(1), 1–12.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Edelsbrunner, HerbertISTA 
;
Hasan, Nany;
Seidel, Raimund;
Shen, Xiao
;
Hasan, Nany;
Seidel, Raimund;
Shen, XiaoAbstract
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.
Publishing Year
Date Published
1989-10-01
Journal Title
Geometriae Dedicata
Acknowledgement
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.
Volume
32
Issue
1
Page
1 - 12
ISSN
eISSN
IST-REx-ID
Cite this
Edelsbrunner H, Hasan N, Seidel R, Shen X. Circles through two points that always enclose many points. Geometriae Dedicata. 1989;32(1):1-12. doi:10.1007/BF00181432
Edelsbrunner, H., Hasan, N., Seidel, R., & Shen, X. (1989). Circles through two points that always enclose many points. Geometriae Dedicata. Springer. https://doi.org/10.1007/BF00181432
Edelsbrunner, Herbert, Nany Hasan, Raimund Seidel, and Xiao Shen. “Circles through Two Points That Always Enclose Many Points.” Geometriae Dedicata. Springer, 1989. https://doi.org/10.1007/BF00181432.
H. Edelsbrunner, N. Hasan, R. Seidel, and X. Shen, “Circles through two points that always enclose many points,” Geometriae Dedicata, vol. 32, no. 1. Springer, pp. 1–12, 1989.
Edelsbrunner H, Hasan N, Seidel R, Shen X. 1989. Circles through two points that always enclose many points. Geometriae Dedicata. 32(1), 1–12.
Edelsbrunner, Herbert, et al. “Circles through Two Points That Always Enclose Many Points.” Geometriae Dedicata, vol. 32, no. 1, Springer, 1989, pp. 1–12, doi:10.1007/BF00181432.
Link(s) to Main File(s)
Access Level
Closed Access
Google Scholar