首页 | 本学科首页   官方微博 | 高级检索  
     


Intersecting Convex Sets by Rays
Authors:Radoslav Fulek  Andreas F. Holmsen  János Pach
Affiliation:(1) School of Computing Science, Simon Fraser University, 8888 University Dr., Burnaby, BC, V6A 1S6, Canada;(2) Division of Computer Science, KAIST, Gwahangno 335, Yuseong-gu, Daejeon, 305-701, Korea;(3) Department of Computer Science, City College of New York, 160 Convent Avenue, New York, NY 10031, USA
Abstract:What is the smallest number τ=τ(n) such that for any collection of n pairwise disjoint convex sets in d-dimensional Euclidean space, there is a point such that any ray (half-line) emanating from it meets at most τ sets of the collection? This question of Urrutia is closely related to the notion of regression depth introduced by Rousseeuw and Hubert (1996). We show the following:Given any collection ({mathcal{C}}) of n pairwise disjoint compact convex sets in d-dimensional Euclidean space, there exists a point p such that any ray emanating from p meets at most (frac{dn+1}{d+1}) members of ({mathcal{C}}).There exist collections of n pairwise disjoint (i) equal-length segments or (ii) disks in the Euclidean plane such that from any point there is a ray that meets at least (frac{2n}{3}-2) of them.We also determine the asymptotic behavior of τ(n) when the convex bodies are fat and of roughly equal size.
Keywords:Convex sets  Geometric transversals  Depth in hyperplane arrangements  Regression depth
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号