2026-07-20T14:43:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4489 2024-03-06T10:35:07Z ddc:004 open_access

Near-Optimal Generalisations of a Theorem of Macbeath Mustafa, Nabil H. Ray, Saurabh Epsilon Nets Cuttings Union Complexity Geometric Set systems Convex Geometry 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nabil H. Mustafa and Saurabh Ray 2014 Is Part Of LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2014.578 urn:nbn:de:0030-drops-44890 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.578 eng https://creativecommons.org/licenses/by/3.0/legalcode