ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. 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 Φ 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 Φ such that any set S' homothetic to S that contains them contains n/c elements of Φ, c a constant (S' is homothetic to S if $S' = \lambda S + {\bf v}$ , where λ is a real number greater than 0 and ${\bf v}$ is a vector of $\Re^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 Φ of n disjoint convex sets in $\Re^3$ such that for any nonempty subset Φ H of Φ there is a sphere S H containing all the elements of Φ H , and no other element of Φ.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009296
Permalink