Piercing convex sets and the Hadwiger-Debrunner (p, q)-problem

Noga Alon, Daniel J. Kleitman

Research output: Contribution to journalArticlepeer-review

122 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 J 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 J. This settles an old problem of Hadwiger and Debrunner.

Original languageEnglish (US)
Pages (from-to)103-112
Number of pages10
JournalAdvances in Mathematics
Volume96
Issue number1
DOIs
StatePublished - Nov 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Piercing convex sets and the Hadwiger-Debrunner (p, q)-problem'. Together they form a unique fingerprint.

Cite this