A combinatorial property of convex sets

被引:9
作者
Abellanas, M
Hernandez, G
Klein, R
NeumannLara, V
Urrutia, J
机构
[1] FERNUNIVERSITAT HAGEN,D-5800 HAGEN,GERMANY
[2] UNIV NACL AUTONOMA MEXICO,MEXICO CITY 04510,DF,MEXICO
[3] UNIV OTTAWA,DEPT COMP SCI,OTTAWA,ON K1N 6N5,CANADA
关键词
D O I
10.1007/PL00009296
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
A known result in combinatorial geometry states that any collection P-n of points on the plane contains two such that any circle containing them contains n/c elements of P-n, c a constant. We prove: Let Phi be a family of n noncrossing compact convex sets on the plane, and let S be a strictly convex compact set. Then there are two elements S-i, S-j of Phi such that any set S' homothetic to S that contains them contains nle elements of Phi, c a constant (S' is homothetic to S if S' = lambda S + v, where lambda is a real number greater than 0 and v is a vector of R(2)). Our proof method is based on a new type of Voronoi diagram, called the ''closest covered set diagram'' based on a convex distance function. We also prove that our result does not generalize to higher dimensions; we construct a set Phi of n disjoint convex sets in R(3) such that for any nonempty subset Phi(H) of Phi there is a sphere S-H containing all the elements of Phi(H), and no other clement of Phi.
引用
收藏
页码:307 / 318
页数:12
相关论文
共 11 条
[1]   A COMBINATORIAL PROPERTY OF POINTS AND ELLIPSOIDS [J].
BARANY, I ;
LARMAN, DG .
DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (04) :375-382
[2]   A COMBINATORIAL RESULT ABOUT POINTS AND BALLS IN EUCLIDEAN-SPACE [J].
BARANY, I ;
SCHMERL, JH ;
SIDNEY, SJ ;
URRUTIA, J .
DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (03) :259-262
[3]  
CHEW P, 1985, P 1 ACM S COMP GEOM, P235
[4]  
EDELSBRUNNER H, 1989, GEOMETRIAE DEDICATA, V32, P1
[5]   INTERVAL ORDERS AND CIRCLE ORDERS [J].
FISHBURN, PC .
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1988, 5 (03) :225-234
[6]  
HYWARD R, 1989, DISCRETE COMPUT GEOM, V4, P263
[7]  
HYWARD R, 1989, DISCRETE COMPUT GEOM, V4, P253
[8]  
ICKLING C, 1993, P 9 ACM S COMP GEOM, P116
[9]   RANDOMIZED INCREMENTAL CONSTRUCTION OF ABSTRACT VORONOI DIAGRAMS [J].
KLEIN, R ;
MEHLHORN, K ;
MEISER, S .
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1993, 3 (03) :157-184
[10]   A COMBINATORIAL RESULT ON POINTS AND CIRCLES ON THE PLANE [J].
NEUMANNLARA, V ;
URRUTIA, J .
DISCRETE MATHEMATICS, 1988, 69 (02) :173-178