Near-Optimal Generalisations of a Theorem of Macbeath

Authors Nabil H. Mustafa, Saurabh Ray



PDF
Thumbnail PDF

File

LIPIcs.STACS.2014.578.pdf
  • Filesize: 0.61 MB
  • 12 pages

Document Identifiers

Author Details

Nabil H. Mustafa
Saurabh Ray

Cite AsGet BibTex

Nabil H. Mustafa and Saurabh Ray. Near-Optimal Generalisations of a Theorem of Macbeath. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 578-589, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.STACS.2014.578

Abstract

The existence of Macbeath regions is a classical theorem in convex geometry ("A Theorem on non-homogeneous lattices", Annals of Math, 1952). We refer the reader to the survey of I. Barany for several applications. 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 espilon-nets for geometric set systems.
Keywords
  • Epsilon Nets
  • Cuttings
  • Union Complexity
  • Geometric Set systems
  • Convex Geometry

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail