Circles through two points that always enclose many points |
| |
Authors: | H. Edelsbrunner N. Hasan R. Seidel X. J. Shen |
| |
Affiliation: | (1) Dept of Computer Science, University of Illinois, 61801 Urbana, Illinois, USA;(2) Dept of Electrical Engineering and Computer Science, University of California, 94720 Berkeley, California, USA;(3) Dept of Computer Science, University of Illinois, 61801 Urbana, Illinois, USA;(4) Dept of Computer Science, East China Institute of Technology, Nanjing, China |
| |
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 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.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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|