Geometric approximation and epsilon-nets

A range space consists of a ground set and a family of allowed subsets, such as intersections with intervals, disks, or axis-aligned rectangles. A heavy range has population fraction at least the chosen positive threshold. An epsilon-net contains at least one point in every such range. Repeated sampled locations can be collapsed for this hitting property. They cannot be discarded from the empirical measure without changing its weights when the goal is a quantitative approximation.

An epsilon-approximation instead bounds the absolute difference between population and sample fractions for every range. It is a stronger kind of measurement, but threshold equality deserves care: an error bound of epsilon alone can allow a range of mass exactly epsilon to have sample mass zero. For example, an epsilon-over-two approximation certainly hits every range of mass at least epsilon. State the exact threshold or margin rather than silently treating a non-strict approximation inequality as a strict hitting guarantee.

A set is shattered when the range family realizes all its subsets. The VC dimension is the maximum size of such a set, or infinity if no finite maximum exists. Intervals on a line have VC dimension two, while planar axis-aligned rectangles have dimension four. Finite dimension limits the number of distinct range traces on a sample. This combinatorial restriction permits a sample-size theorem independent of the original population size, despite the requirement to hit every heavy range simultaneously.

For a fixed range space of finite VC dimension v at least one, take epsilon and failure probability strictly between zero and one half. There is a universal constant such that an independent uniform sample with replacement of at least the displayed size is an epsilon-net with probability at least one minus the failure probability. The constant is not specified here, so the asymptotic expression is not a numerical sample-size recipe. The proof uses trace counting and a double-sampling argument; bounding the miss probability of one predetermined range is not the full uniform theorem.

A coreset is defined relative to an objective family. For directional width, a subset K is an epsilon-kernel when its width in every unit direction lies between one minus epsilon times the original width and the original width. The upper inequality follows from being a subset; the lower inequality must be proved uniformly over directions. A range-hitting guarantee does not establish this multiplicative width condition, just as retaining extreme points in a few directions does not automatically control all other directions.

Conversely, preserving widths does not guarantee accurate range counts. A few extreme points may retain the hull while missing nearly all population mass. The right summary therefore depends on the downstream question: coverage, counting, nearest-neighbor approximation, or an optimization objective. Include the metric, dimension, range family, weighting, and probability guarantee in the specification. A visual impression of even coverage or a successful test on a few ranges is not evidence for a simultaneous theorem over the entire family.