claimroutineinferred_dep

Sweep pieces avoid sampled circles and cover points

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

Statement (paper)

Each piece produced by the sweep is an open region between two fixed semicircle graphs (or infinite boundaries) over an open interval and contains no part of a sampled circle. Moreover, every input point not lying on a sampled circle belongs to one of these open pieces.

In plain English

Each piece from the left-to-right sweep is an open region between two fixed semicircle graphs (or infinite boundaries) over an open interval, and it meets no sampled circle. Every input point not on a sampled circle lies in one of these open pieces.

Why it's here

This shows the sweep decomposition is a valid region assignment for the cutting lemma: the pieces are simple regions free of sampled circles, and they cover all remaining points. It relies on the generic horizontal direction from the previous claim, so that input points do not share abscissas with critical points of the arrangement. The piece-count and conflict-bound claims then apply to this decomposition.
Classified routine:
Standard vertical-decomposition (trapezoidal decomposition) argument for arrangements of curves, as in the Clarkson–Shor random-sampling cutting construction; it follows directly from the generic-direction choice in the previous claim.

Uses

claimGeneric horizontal direction exists

Used by

claimSweep produces O(1+s^2) piecesclaimConflict bound via union over candidate regions

Sources

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

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    outline: "Sweep pieces avoid sampled circles, cover points" rests on claim-inc-cutting-1