Abstract
Let S be a family of compact convex sets in Rd. Let D(S) be the largest diameter of any member of S. The family S is ε-separated if, for every 0<k<d, any k of the sets can be separated from any other d-k of the sets by a hyperplane more than ε/D(S) away from all d of the sets. We prove that if S is an ε-separated family of at least N(ε) compact convex sets in Rd and every 2d+2 members of S are met by a hyperplane, then there is a hyperplane meeting all the members of S. The number N(ε) depends both on the dimension d and on the separation parameter ε. This is the first Helly-type theorem known for hyperplane transversals to compact convex sets of arbitrary shape in dimension greater than one.
Original language | English (US) |
---|---|
Pages | 57-63 |
Number of pages | 7 |
State | Published - 2000 |
Event | 16th Annual Symposium on Computational Geometry - Hong Kong, Hong Kong Duration: Jun 12 2000 → Jun 14 2000 |
Other
Other | 16th Annual Symposium on Computational Geometry |
---|---|
City | Hong Kong, Hong Kong |
Period | 6/12/00 → 6/14/00 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics