propositionstandard

Szemerédi–Trotter bound for unit circles

Proposition·inc:incidence·§2.2 Cuttings and the incidence bound

Statement (paper)

For

m

distinct points and

l

distinct unit circles in the plane,

I\le C\log^2(2+m+l) \bigl(m^{2/3}l^{2/3}+m+l\bigr),

where

C

is an absolute constant. In particular, when

m,l

are bounded by a fixed power of

t

, the logarithmic factor is

(\log t)^{O(1)}

In plain English

The number

I

of incidences between

m

distinct points and

l

distinct unit circles in the plane is at most

C\log^2(2+m+l)\,(m^{2/3}l^{2/3}+m+l)

for an absolute constant

C

. When

m,l

are at most a fixed power of

t

, the log factor is

(\log t)^{O(1)}

Why it's here

This is the incidence input for the cutting arguments in the paper. It gives the Szemerédi–Trotter-type exponents

m^{2/3}l^{2/3}+m+l

for unit circles, losing only polylogarithmic factors, which are harmless at the

t^{o(1)}

scale. Later steps use it to bound incidences inside the pieces of a cutting and to show that some small piece must carry many incidences.

Classified standard:

Point–unit-circle incidence bound of Szemerédi–Trotter type (Spencer–Szemerédi–Trotter 1984, via cuttings as in Clarkson–Edelsbrunner–Guibas–Sharir–Welzl 1990). This is stated here with a harmless polylog loss.

Uses

Nothing else in the paper

Used by

propIncidence piece with degree and expansion controlclaimSome small piece carries many incidencesclaimTrimming high-degree vertices gives degree boundsclaimPreliminary square-root expansion bound

Sources

PaperOpen

Section: §2.2 Cuttings and the incidence bound
Page: —
Label: inc:incidence
Line: sections/01-incidence.tex:146

Leannot aligned

Phase 2 aligns this node to a Lean declaration.