Piercing convex sets

Noga Alon, Daniel J. Kleitman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationEighth Annual Symposium On Computational Geometry
PublisherPubl by ACM
Pages157-160
Number of pages4
ISBN (Print)0897915178, 9780897915175
DOIs
StatePublished - 1992
Externally publishedYes
EventEighth Annual Symposium On Computational Geometry - Berlin, Ger
Duration: Jun 10 1992Jun 12 1992

Publication series

NameEighth Annual Symposium On Computational Geometry

Other

OtherEighth Annual Symposium On Computational Geometry
CityBerlin, Ger
Period6/10/926/12/92

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Piercing convex sets'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., & Kleitman, D. J. (1992). Piercing convex sets. In Eighth Annual Symposium On Computational Geometry (pp. 157-160). (Eighth Annual Symposium On Computational Geometry). Publ by ACM. https://doi.org/10.1145/142675.142711