Intersecting Convex Sets by Rays

Abstract

What is the smallest number tau = tau(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 tau 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 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 dn+1/d+1 members of 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 2n/3-2 of them. We also determine the asymptotic behavior of tau(n) when the convex bodies are fat and of roughly equal size.