lemmastandard

Random-sampling cutting for unit circles

Lemma·inc:cutting·§2.2 Cuttings and the incidence bound

Statement (paper)

Let P\mathcal P be a finite planar point set and let Q\mathcal Q be a nonempty set of ll distinct unit circles. For every R≥1R\ge1, sample s=⌈CRlog⁡(2+l)⌉s=\lceil C R\log(2+l)\rceil circles independently and uniformly with replacement, where CC is a sufficiently large absolute constant. With probability at least 9/109/10, after deleting the points on sampled circles, all remaining points can be assigned to at most C′(1+s2)C'(1+s^2) open regions, each of which intersects at most l/Rl/R of the original circles. Each assigned point belongs to its assigned region.

In plain English

Sample s=⌈CRlog⁡(2+l)⌉s=\lceil CR\log(2+l)\rceil of ll distinct unit circles uniformly with replacement. With probability at least 9/109/10, after deleting points on sampled circles, the remaining points can be assigned to at most C′(1+s2)C'(1+s^2) open regions, each containing its assigned points and meeting at most l/Rl/R of the original circles.

Why it's here

This is a cutting lemma for unit circles, obtained by random sampling: a left-to-right sweep of the sampled circles gives O(1+s2)O(1+s^2) regions, and a union bound over polynomially many candidate regions shows each one meets few original circles. Later results use it to split the point set into small pieces at the cost of deleting the points on the sampled circles.
Classified standard:
This is the classical random-sampling (ε-net) cutting construction of Clarkson–Shor (1989) and Clarkson et al. (1990), specialized to unit circles. The paper re-derives it here and uses it in the usual way to obtain the Szemerédi–Trotter/Spencer–Szemerédi–Trotter incidence bound.

Uses

Nothing else in the paper

Used by

propIncidence piece with degree and expansion controlclaimCutting deletion loses few incidences

Inside the proof

claimGeneric horizontal direction existsclaimSweep pieces avoid sampled circles and cover pointsclaimSweep produces O(1+s^2) piecesclaimConflict bound via union over candidate regions

Sources

PaperOpen
Section
§2.2 Cuttings and the incidence bound
Page
—
Label
inc:cutting
Line
sections/01-incidence.tex:73
Leannot aligned

Phase 2 aligns this node to a Lean declaration.