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


Intersecting Convex Sets by Rays
Authors:Radoslav Fulek  Andreas F Holmsen  János Pach
Institution:(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号