Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

A combinatorial property of convex sets

M. AbellanasContact Information, G. HernandezContact Information, R. KleinContact Information, V. Neumann-LaraContact Information and J. UrrutiaContact Information

(1)  Dept. de Matemática Aplicada, Universidad Politecnica de Madrid, Campus de Montegancedo, s/n, Boadilla del Monte, 28660 Madrid, Spain
(2)  Praktische Informatik VI, Fern Universität Hagen, Elberfelder Strasse 95, 5800 Hagen, Germany
(3)  Universidad Nacional Antonoma de México, Mexico
(4)  Department of Computer Science, University of Ottawa, KIN 6N5 Ottawa, Ontario, Canada

Received: 7 December 1994  Revised: 25 March 1996  

Abstract  A known result in combinatorial geometry states that any collection Pn of points on the plane contains two such that any circle containing them contains n/c elements of Pn, 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 Si, Sj 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 5’ = λS + v, where λ is a real number greater than 0 and v is a vector of ℜ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 ℜ3)3 such that for any nonempty subset ΦHh of Φ there is a sphere SH containing all the elements of ΦH, and no other element of Φ.

Contact Information M. Abellanas (Corresponding author)
Email: mavellanas@fi.upm.es

Contact Information G. Hernandez (Corresponding author)
Email: gregorio@fi.upm.es

Contact Information R. Klein (Corresponding author)
Email: Rolf.Klein@FernUni-Hagen.de

Contact Information J. Urrutia (Corresponding author)
Email: Jorge@csi.uottawa.ca
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this article
Export this article as RIS | Text
 
Remote Address: 38.107.191.108 • Server: mpweb23
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)