claimroutineinferred_dep

Sweep produces O(1+s^2) pieces

Claim·§2.2 Cuttings and the incidence bound·inside lemRandom-sampling cutting for unit circles

Statement (paper)

The number of open pieces produced by the left-to-right sweep of the gaps is O(1+s2)O(1+s^2), including in the presence of multiple intersections or several events with the same abscissa.

In plain English

The left-to-right sweep over the gaps between sampled circles produces only O(1+s2)O(1+s^2) open pieces. This holds even when several intersections or other events share the same abscissa.

Why it's here

This bounds the number of regions in the cutting lemma by C′(1+s2)C'(1+s^2), as the parent statement requires. The count comes from the number of events (endpoints and pairwise intersections of the ss sampled unit circles, which is O(1+s2)O(1+s^2)) together with the fact that coincident events do not add extra pieces.
Classified routine:
Standard vertical-decomposition / trapezoidal sweep counting for arrangements of s pseudo-circles (as in Clarkson–Shor style cuttings): the number of pieces is linear in the number of vertices and arcs, which is O(1+s^2).

Uses

claimSweep pieces avoid sampled circles and cover points

Used by

Nothing in the paper

Sources

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

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    outline: "Number of pieces is O(1+s^2)" rests on claim-inc-cutting-2