ε -Mnets: Hitting Geometric Set Systems with Subsets

Nabil H. Mustafa; Saurabh Ray

doi:10.1007/s00454-016-9845-8

ε -Mnets: Hitting Geometric Set Systems with Subsets

Nabil H. Mustafa, Saurabh Ray

Computer Science

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	625-640
Number of pages	16
Journal	Discrete and Computational Geometry
Volume	57
Issue number	3
DOIs	https://doi.org/10.1007/s00454-016-9845-8
State	Published - 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

Access to Document

10.1007/s00454-016-9845-8

Cite this

@article{ad9d75a1c53a43898f6c64555f16b531,

title = "ε -Mnets: Hitting Geometric Set Systems with Subsets",

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.",

keywords = "Epsilon-nets, Geometric set systems, Hitting sets, Macbeath regions",

author = "Mustafa, {Nabil H.} and Saurabh Ray",

note = "Publisher Copyright: {\textcopyright} 2016, Springer Science+Business Media New York.",

year = "2017",

month = apr,

day = "1",

doi = "10.1007/s00454-016-9845-8",

language = "English (US)",

volume = "57",

pages = "625--640",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - ε -Mnets

T2 - Hitting Geometric Set Systems with Subsets

AU - Mustafa, Nabil H.

AU - Ray, Saurabh

PY - 2017/4/1

Y1 - 2017/4/1

N2 - 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.

AB - 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.

KW - Epsilon-nets

KW - Geometric set systems

KW - Hitting sets

KW - Macbeath regions

UR - http://www.scopus.com/inward/record.url?scp=85001755145&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85001755145&partnerID=8YFLogxK

U2 - 10.1007/s00454-016-9845-8

DO - 10.1007/s00454-016-9845-8

M3 - Article

AN - SCOPUS:85001755145

SN - 0179-5376

VL - 57

SP - 625

EP - 640

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 3

ER -

ε -Mnets: Hitting Geometric Set Systems with Subsets

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this