Incidence geometry

Incidence geometry studies which points lie on which curves, lines or higher-dimensional objects and how many such incidences a finite configuration can have.

A linear space is a structure in incidence geometry with a set of points and a collection of subsets called lines: any two distinct points lie on exactly one line, and every line contains at least two points. The lines here are incidence-theoretic objects, without a required coordinate realization. A finite linear space imposes finiteness; its nontrivial form excludes a line containing all points. This is distinct from a vector space, whose structure involves addition and scalar multiplication.

For distinct real affine lines in ${\mathbb{R}}^n$, $n\ge 2$, a joint of a line collection is a point lying on $n$ lines with linearly independent direction vectors. In three dimensions the directions must not all lie in one plane. Extra incident lines are allowed; existence of one spanning choice is enough. This counts joint of a line collection points, rather than tuples of lines or incidence multiplicities.

The number of joints of a line collection formed by $L$ distinct real affine lines in ${\mathbb{R}}^n$ is at most $C_n{L}^{n/(n-1)}$. The pruning and minimal-degree polynomial argument proves this bound. The exponent is sharp: the coordinate-line grid has $m^n$ joints of a line collection and $n{m}^{n-1}$ lines. In three dimensions the bound is $C{L}^{3/2}$.

Let a line collection have $M$ joints of a line collection and put $D=\lceil n{M}^{1/n}\rceil$. If $M>LD$, deleting each line with at most $D$ current joints of a line collection, together with those joints of a line collection, leaves a nonempty configuration in which every line has more than $D$ joints of a line collection. A nonzero polynomial of degree at most $D$ vanishes on the retained joints of a line collection by rank-nullity theorem. Choose one of minimum degree. Its restriction vanishes identically on every retained line, so its gradient is orthogonal to a spanning set of directions at every joint of a line collection and hence vanishes there. Each nonzero partial derivative would be a lower-degree polynomial with the same zeros, contradicting minimality. In characteristic zero, all derivatives vanishing forces a constant polynomial, another contradiction. Therefore $M\le LD$, giving the joints theorem. The argument's characteristic-zero assumption is essential to its derivative step.

A bounded subset of ${\mathbb{R}}^n$ is a Kakeya set if it contains a unit line segment in every direction. Segment positions may vary with direction. Such a set need not have positive Lebesgue measure; the dimension problem concerns its Minkowski dimension or other notions of dimension.

A Besicovitch set is a planar Kakeya set of Lebesgue measure zero containing a unit line segment in every direction.

Choose a compact $K\subset [0,1]\times \mathbb{R}$ with full horizontal projection and zero-length projections $y+tx$ for $t\in [0,1]$. Then the displayed set is compact, has zero area by the Fubini theorem, and contains a segment of every slope in $[0,1]$. Such parameter sets exist by the Baire category theorem in the Hausdorff metric: fine parallel segments approximate any parameter set while making a fixed band of projections uniformly small. Finite grids and a countable intersection make every required projection null. Four rotated copies supply every planar direction.

A Perron tree is a finite triangular splitting-and-sliding arrangement retaining a prescribed angular range while overlapping its pieces strongly. The compression parameter and the number of generations can make union area an arbitrarily small fraction of total piece area. Suitable longitudinal extensions separate the pieces into disjoint rectangles. This stronger finite geometry is used by the ball-multiplier counterexample; a compact measure-zero Besicovitch set alone does not assert that arbitrary segment translates are disjoint.

The dimension assertion asks that every bounded Kakeya set in ${\mathbb{R}}^n$ have full Minkowski dimension. The Kakeya maximal conjecture implies the stronger lower-dimension conclusion: its application to $E_{\delta }$ gives $|E_{\delta }|{\gtrsim }_{n,\epsilon }{\delta }^{n\epsilon }$, hence $N_{\delta }(E){\gtrsim }_{n,\epsilon }{\delta }^{-n+n\epsilon }$ for every $\epsilon >0$.

A Kakeya tube is a neighborhood of transverse radius $\delta$ of a line segment of fixed unit length. Round cross-sections and comparable rectangular cross-sections are interchangeable up to fixed constants. The tube has Lebesgue measure comparable to ${\delta }^{n-1}$ in ${\mathbb{R}}^n$.

Relative to a finite point set, an ordinary line is a line containing exactly two points of that set. It is an exact-richness condition, not a count of unordered pairs alone: a line with three points contains three point pairs but is not ordinary. Point-line duality turns ordinary lines into intersections incident to exactly two dual lines.

If a finite planar point set has at most $Kn$ ordinary lines, its points can be covered by $O(K+1)$ possibly reducible cubics. The Euler defect identity for a projective line arrangement gives $O(Kn)$ bad edges in the dual. Bounded-radius propagation of edge defects and averaging select one dual line with $O(K+1)$ unsafe edges. Cubic propagation along a triangular strip covers each safe run; each exceptional intersection vertex represents a primal line, covered by a degenerate cubic containing a line. A dual line with very few intersection vertices instead yields a direct covering by few primal lines.

For a finite planar point set $P$, its distinct-distance set is $\Delta (P)=\{|p-q|:p,q\in P\}$. It includes zero for nonempty $P$. Its cardinality measures how many different distances the configuration determines. Ordered point pairs can be grouped according to their distance, which relates the problem to incidences between points and curves.

For a finite set of at least two points in the plane, some point determines the displayed number of different positive Euclidean distances. The circular-arc graph for distinct distances has quadratically many edges. The rich-bisector deletion bound removes high-multiplicity edges while retaining that order of growth. The crossing lemma for multigraphs then compares its lower crossing bound with the quadratic count of pairs of circles. This strengthens the corresponding bound for the whole distinct-distance set. The original result is Theorem11 of Székely's 1997 paper.

Around each of $n$ points draw its at most $t$ distinct-distance circles. On every circle containing at least three points, join cyclically consecutive points by arcs. The resulting loopless multigraph has at least $n(n-1)-2nt$ edges and a drawing with $O(n^2{t}^2)$ crossings. A pair joined by several arcs has every corresponding centre on its perpendicular bisector, which is the key to bounding multiplicity.

Every supporting centre of an arc between fixed endpoints lies on their perpendicular bisector. Multiplicity at least $k$ therefore makes that line contain at least $k$ of the original points. For each such line containing $s$ points, its $s$ centres each support at most $t$ circles; on one circle at most two consecutive-point arcs have that symmetry axis. The rich line bound summed over dyadic occupancies gives the displayed bound.

For every positive distance, draw equal-radius circles centred at the points of $P$. Their incidences between points and curves count the ordered pairs at that distance. The Szemerédi–Trotter theorem for unit circles bounds each distance class by $O(|P{|}^{4/3})$. Summing over all classes accounts for $|P|(|P|-1)$ pairs, proving $|\Delta (P)|\gtrsim |P{|}^{2/3}$.

For finite sets of points $P$ and geometric curves $\mathcal{C}$, a point-curve incidence is a pair $(p,\gamma )$ with $p\in \gamma$. The incidence count is $I(P,\mathcal{C})={\sum }_{\gamma \in \mathcal{C}}|P\cap \gamma |$. Bounds in incidence geometry exploit restrictions on how curves can meet points, rather than treating the incidence relation as an arbitrary bipartite graph.

If $n$ points and $m$ curves have the property that each pair of distinct points lies on at most $\lambda$ curves, then double counting gives ${\sum }_{\gamma }{k}_{\gamma }(k_{\gamma }-1)\le \lambda n(n-1)$, where $k_{\gamma }=|P\cap \gamma |$. The Cauchy-Schwarz inequality implies $I^2\le mI+\lambda mn(n-1)$ and hence $I\le m+\sqrt{\lambda mn(n-1)}$. The statement needs only this combinatorial multiplicity condition, not algebraicity.

For $m$ lines and $n$ points in the real plane, the number of point-line incidences isConnecting consecutive incidence points on each line and applying the Crossing lemma proves the bound.

For $n$ distinct points in the real plane, $L_{\ge k}$ counts lines containing at least $k\ge 2$ points. The Szemerédi–Trotter theorem applied to these lines gives the bound by absorbing its additive line-count term; bounded $k$ follows by counting point pairs. Consequently, summing occupancies of lines with at least $k$ points by dyadic ranges gives $O(n^2/k^2+n\log n)$.

For distinct equal-radius circles and a finite point set in the real plane, incidences between points and curves satisfy $I(P,\mathcal{C})=O(|P{|}^{2/3}|\mathcal{C}{|}^{2/3}+|P|+|\mathcal{C}|)$. Scaling the plane reduces any common positive radius to one. The constant is universal. The fixed-radius condition bounds the number of circles through two prescribed distinct points by two.

For $m$ distinct real univariate polynomials of degree at most $d$ and $n$ points with distinct first coordinates, the number of incidences between the points and the polynomial graphs isTwo polynomial graphs meet at most $d$ times, so the graph formed from consecutive incidences has $O(d{m}^2)$ crossings; the Crossing lemma supplies the lower bound.