کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4655114 | 1632938 | 2015 | 15 صفحه PDF | دانلود رایگان |
Given a finite family of sets, Hall's classical marriage theorem provides a necessary and sufficient condition for the existence of a system of distinct representatives for the sets in the family. Here we extend this result to a geometric setting: given a finite family of objects in the Euclidean space (e.g., convex bodies), we provide a sufficient condition for the existence of a system of distinct representatives for the objects that are also distant from each other. For a wide variety of geometric objects, this sufficient condition is also necessary in an asymptotic sense (i.e., apart from constant factors, the inequalities are the best possible). Our methods are constructive and lead to efficient algorithms for computing such representatives.
Journal: Journal of Combinatorial Theory, Series A - Volume 134, August 2015, Pages 36–50