Circles through two points that always enclose many points期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Circles through two points that always enclose many points

Authors:	H Edelsbrunner N Hasan R Seidel X J Shen

Institution:	(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 $n\left( {1/2 - 1\sqrt {12} } \right) + O(1) \approx n/4 \cdot 7$ 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 等数据库收录！