Near-optimal generalisations of a theorem of Macbeath

Nabil H. Mustafa, Saurabh Ray

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publication31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014
EditorsNatacha Portier, Ernst W. Mayr
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages578-589
Number of pages12
Volume25
ISBN (Electronic)9783939897651
DOIs
StatePublished - Mar 1 2014
Event31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014 - Lyon, France
Duration: Mar 5 2014Mar 8 2014

Other

Other31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014
CountryFrance
CityLyon
Period3/5/143/8/14

Keywords

  • Convex Geometry
  • Cuttings
  • Epsilon Nets
  • Geometric Set systems
  • Union Complexity

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Near-optimal generalisations of a theorem of Macbeath'. Together they form a unique fingerprint.

  • Cite this

    Mustafa, N. H., & Ray, S. (2014). Near-optimal generalisations of a theorem of Macbeath. In N. Portier, & E. W. Mayr (Eds.), 31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014 (Vol. 25, pp. 578-589). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.STACS.2014.578