Piercing convex sets

Noga Alon; Daniel J. Kleitman

doi:10.1145/142675.142711

Piercing convex sets

Noga Alon, Daniel J. Kleitman

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 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 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 F. This extends Helly's Theorem and settles an old problem of Hadwiger and Debrunner.

Original language	English (US)
Title of host publication	Eighth Annual Symposium On Computational Geometry
Publisher	Publ by ACM
Pages	157-160
Number of pages	4
ISBN (Print)	0897915178, 9780897915175
DOIs	https://doi.org/10.1145/142675.142711
State	Published - 1992
Externally published	Yes
Event	Eighth Annual Symposium On Computational Geometry - Berlin, Ger Duration: Jun 10 1992 → Jun 12 1992

Publication series

Name	Eighth Annual Symposium On Computational Geometry

Other

Other	Eighth Annual Symposium On Computational Geometry
City	Berlin, Ger
Period	6/10/92 → 6/12/92

All Science Journal Classification (ASJC) codes

General Engineering

Access to Document

10.1145/142675.142711

Cite this

@inproceedings{45f2d33218ce461486708c0ff7139d65,

title = "Piercing convex sets",

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

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

year = "1992",

doi = "10.1145/142675.142711",

language = "English (US)",

isbn = "0897915178",

series = "Eighth Annual Symposium On Computational Geometry",

publisher = "Publ by ACM",

pages = "157--160",

booktitle = "Eighth Annual Symposium On Computational Geometry",

note = "Eighth Annual Symposium On Computational Geometry ; Conference date: 10-06-1992 Through 12-06-1992",

}

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 -

Piercing convex sets

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this