Abstract
A family of sets has the (p, q) property if among any p members of the family some q have a nonempty intersection. The authors have proved that for every p ≥ q ≥ d + 1 there is a c = c(p, q, d) < ∞ such that for every family F of compact, convex sets in Rd which has the (p, q) property there is a set of at most c points in Rd that intersects each member of F, thus settling an old problem of Hadwiger and Debrunner. Here we present a purely combinatorial proof of this result.
Original language | English (US) |
---|---|
Article number | R1 |
Pages (from-to) | 1-8 |
Number of pages | 8 |
Journal | Electronic Journal of Combinatorics |
Volume | 4 |
Issue number | 2 R |
State | Published - 1997 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics