ε -Mnets: Hitting Geometric Set Systems with Subsets

Nabil H. Mustafa, Saurabh Ray

Research output: Contribution to journalArticlepeer-review

Abstract

The existence of Macbeath regions is a classical theorem in convex geometry (Macbeath in Ann Math 56:269–293, 1952), with recent applications in discrete and computational geometry. In this paper, we initiate the study of Macbeath regions in a combinatorial setting and establish near-optimal bounds for several basic geometric set systems.

Original languageEnglish (US)
Pages (from-to)625-640
Number of pages16
JournalDiscrete and Computational Geometry
Volume57
Issue number3
DOIs
StatePublished - Apr 1 2017

Keywords

  • Epsilon-nets
  • Geometric set systems
  • Hitting sets
  • Macbeath regions

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'ε -Mnets: Hitting Geometric Set Systems with Subsets'. Together they form a unique fingerprint.

Cite this