Near-optimal generalisations of a theorem of Macbeath

Nabil H. Mustafa; Saurabh Ray

doi:10.4230/LIPIcs.STACS.2014.578

Near-optimal generalisations of a theorem of Macbeath

Nabil H. Mustafa, Saurabh Ray

Computer Science

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

Abstract

The existence of Macbeath regions is a classical theorem in convex geometry ("A Theorem on nonhomogeneous lattices", Annals of Math, 1952). We refer the reader to the survey of I. Barany for several applications [3]. Recently there have been some striking applications of Macbeath regions in discrete and computational geometry. In this paper, we study Macbeath's problem in a more general setting, and not only for the Lebesgue measure as is the case in the classical theorem. We prove near-optimal generalizations for several basic geometric set systems. The problems and techniques used are closely linked to the study of ε-nets for geometric set systems.

Original language	English (US)
Title of host publication	31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014
Editors	Ernst W. Mayr, Natacha Portier
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	578-589
Number of pages	12
Volume	25
ISBN (Electronic)	9783939897651
DOIs	https://doi.org/10.4230/LIPIcs.STACS.2014.578
State	Published - Mar 1 2014
Event	31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014 - Lyon, France Duration: Mar 5 2014 → Mar 8 2014

Other

Other	31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014
Country/Territory	France
City	Lyon
Period	3/5/14 → 3/8/14

Keywords

Convex Geometry
Cuttings
Epsilon Nets
Geometric Set systems
Union Complexity

ASJC Scopus subject areas

Software

Access to Document

10.4230/LIPIcs.STACS.2014.578

Cite this

Near-optimal generalisations of a theorem of Macbeath. / Mustafa, Nabil H.; Ray, Saurabh.
31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014. ed. / Ernst W. Mayr; Natacha Portier. Vol. 25 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2014. p. 578-589.

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

Mustafa, NH & Ray, S 2014, Near-optimal generalisations of a theorem of Macbeath. in EW Mayr & N Portier (eds), 31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014. vol. 25, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 578-589, 31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014, Lyon, France, 3/5/14. https://doi.org/10.4230/LIPIcs.STACS.2014.578

@inproceedings{497ea74c196b4cc2b9a2ac848bcf2bee,

title = "Near-optimal generalisations of a theorem of Macbeath",

abstract = "The existence of Macbeath regions is a classical theorem in convex geometry ({"}A Theorem on nonhomogeneous lattices{"}, Annals of Math, 1952). We refer the reader to the survey of I. Barany for several applications [3]. Recently there have been some striking applications of Macbeath regions in discrete and computational geometry. In this paper, we study Macbeath's problem in a more general setting, and not only for the Lebesgue measure as is the case in the classical theorem. We prove near-optimal generalizations for several basic geometric set systems. The problems and techniques used are closely linked to the study of ε-nets for geometric set systems.",

keywords = "Convex Geometry, Cuttings, Epsilon Nets, Geometric Set systems, Union Complexity",

author = "Mustafa, {Nabil H.} and Saurabh Ray",

note = "Publisher Copyright: {\textcopyright} Nabil H. Mustafa and Saurabh Ray;.; 31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014 ; Conference date: 05-03-2014 Through 08-03-2014",

year = "2014",

month = mar,

day = "1",

doi = "10.4230/LIPIcs.STACS.2014.578",

language = "English (US)",

volume = "25",

pages = "578--589",

editor = "Mayr, {Ernst W.} and Natacha Portier",

booktitle = "31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

}

TY - GEN

T1 - Near-optimal generalisations of a theorem of Macbeath

AU - Mustafa, Nabil H.

AU - Ray, Saurabh

N1 - Publisher Copyright: © Nabil H. Mustafa and Saurabh Ray;.

PY - 2014/3/1

Y1 - 2014/3/1

N2 - The existence of Macbeath regions is a classical theorem in convex geometry ("A Theorem on nonhomogeneous lattices", Annals of Math, 1952). We refer the reader to the survey of I. Barany for several applications [3]. Recently there have been some striking applications of Macbeath regions in discrete and computational geometry. In this paper, we study Macbeath's problem in a more general setting, and not only for the Lebesgue measure as is the case in the classical theorem. We prove near-optimal generalizations for several basic geometric set systems. The problems and techniques used are closely linked to the study of ε-nets for geometric set systems.

AB - The existence of Macbeath regions is a classical theorem in convex geometry ("A Theorem on nonhomogeneous lattices", Annals of Math, 1952). We refer the reader to the survey of I. Barany for several applications [3]. Recently there have been some striking applications of Macbeath regions in discrete and computational geometry. In this paper, we study Macbeath's problem in a more general setting, and not only for the Lebesgue measure as is the case in the classical theorem. We prove near-optimal generalizations for several basic geometric set systems. The problems and techniques used are closely linked to the study of ε-nets for geometric set systems.

KW - Convex Geometry

KW - Cuttings

KW - Epsilon Nets

KW - Geometric Set systems

KW - Union Complexity

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

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

U2 - 10.4230/LIPIcs.STACS.2014.578

DO - 10.4230/LIPIcs.STACS.2014.578

M3 - Conference contribution

AN - SCOPUS:84907854355

VL - 25

SP - 578

EP - 589

BT - 31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014

A2 - Mayr, Ernst W.

A2 - Portier, Natacha

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014

Y2 - 5 March 2014 through 8 March 2014

ER -

Near-optimal generalisations of a theorem of Macbeath

Abstract

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this