TY - GEN

T1 - Piercing convex sets

AU - Alon, Noga

AU - Kleitman, Daniel J.

PY - 1992

Y1 - 1992

N2 - A family of sets has the (p,q) property if among any p members of the family some q have a nonempty intersection. It is shown 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. This extends Helly's Theorem and settles an old problem of Hadwiger and Debrunner.

AB - A family of sets has the (p,q) property if among any p members of the family some q have a nonempty intersection. It is shown 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. This extends Helly's Theorem and settles an old problem of Hadwiger and Debrunner.

UR - http://www.scopus.com/inward/record.url?scp=0026995270&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026995270&partnerID=8YFLogxK

U2 - 10.1145/142675.142711

DO - 10.1145/142675.142711

M3 - Conference contribution

AN - SCOPUS:0026995270

SN - 0897915178

SN - 9780897915175

T3 - Eighth Annual Symposium On Computational Geometry

SP - 157

EP - 160

BT - Eighth Annual Symposium On Computational Geometry

PB - Publ by ACM

T2 - Eighth Annual Symposium On Computational Geometry

Y2 - 10 June 1992 through 12 June 1992

ER -