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

Noga Alon; Daniel J. Kleitman

doi:10.1016/0001-8708(92)90052-M

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

Noga Alon
, Daniel J. Kleitman

Research output: Contribution to journal › Article › peer-review

139 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 R^d which has the (p, q) property there is a set of at most c points in R^d that intersects each member of J. This settles an old problem of Hadwiger and Debrunner.

Original language	English (US)
Pages (from-to)	103-112
Number of pages	10
Journal	Advances in Mathematics
Volume	96
Issue number	1
DOIs	https://doi.org/10.1016/0001-8708(92)90052-M
State	Published - Nov 1992
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics

Access to Document

10.1016/0001-8708(92)90052-M

Cite this

@article{6f83aa718446445e853c953c045a9ea4,

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

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.",

author = "Noga Alon and Kleitman, \{Daniel J.\}",

note = "Funding Information: * Research supported in part by Grant, and a U.S. Air Force Ofice",

year = "1992",

month = nov,

doi = "10.1016/0001-8708(92)90052-M",

language = "English (US)",

volume = "96",

pages = "103--112",

journal = "Advances in Mathematics",

issn = "0001-8708",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

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

AU - Alon, Noga

AU - Kleitman, Daniel J.

N1 - Funding Information: * Research supported in part by Grant, and a U.S. Air Force Ofice

PY - 1992/11

Y1 - 1992/11

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 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.

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 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.

UR - https://www.scopus.com/pages/publications/38249009255

UR - https://www.scopus.com/pages/publications/38249009255#tab=citedBy

U2 - 10.1016/0001-8708(92)90052-M

DO - 10.1016/0001-8708(92)90052-M

M3 - Article

AN - SCOPUS:38249009255

SN - 0001-8708

VL - 96

SP - 103

EP - 112

JO - Advances in Mathematics

JF - Advances in Mathematics

IS - 1

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this