文章基本信息

标题：Near-Optimal Generalisations of a Theorem of Macbeath
本地全文：下载
作者：Nabil H. Mustafa ; Saurabh Ray
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：25
页码：578-589
DOI：10.4230/LIPIcs.STACS.2014.578
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Epsilon Nets; Cuttings; Union Complexity; Geometric Set systems; Convex Geometry