Epsilon-Mnets: Hitting Geometric Set Systems with Subsets

Nabil Mustafa (1) , Saurabh Ray (2)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 NYU

The existence of Macbeath regions is a classical theorem in convex geometry [13], with recent applications in discrete and computational geometry. In this paper, we initiate the study of Macbeath regions in a combinatorial setting—and not only for the Lebesgue measure as is the case in the classical theorem—and establish near-optimal bounds for several basic geometric set systems.

Domaines: Informatique

Nabil Mustafa, Saurabh Ray. Epsilon-Mnets: Hitting Geometric Set Systems with Subsets. Discrete and Computational Geometry, 2017, ⟨10.1007/s00454-016-9845-8⟩. ⟨hal-01468731⟩