Epsilon-approximations and epsilon-nets

2017/02/13 by Mustafa, Nabil H., Varadarajan, Kasturi R. · 2 citations
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1702.03676

Abstract

The use of random samples to approximate properties of geometric configurations has been an influential idea for both combinatorial and algorithmic purposes. This chapter considers two related notions---ε-approximations and ε-nets---that capture the most important quantitative properties that one would expect from a random sample with respect to an underlying geometric configuration.

Cited by

• Summarizing Classed Region Maps with a Disk Choreme
• On Fair Epsilon Net and Geometric Hitting Set

Related

• Carnival of Samplings: Nets, Approximations, Relative and Sensitive
• Weighted Epsilon-Nets
• Online Epsilon Net and Piercing Set for Geometric Concepts
• Too Many or Too Few? Sampling Bounds for Topological Descriptors
• A Note on Approximate Nearest Neighbor Methods