Geometric Duality, Line Arrangements, Levels, and Discrepancy

Geometric Duality, Line Arrangements, Levels, and Discrepancy

Part 17 used a geometric duality of its own: Delaunay edges encode adjacency between Voronoi cells. Here we make a different duality explicit—one that exchanges points and lines. It turns questions about collinearity, slopes, and halfplanes into questions about intersections, vertical order, and paths through an arrangement.

That exchange is more than a clever proof trick. Once a set of lines has been decomposed into vertices, edges, and faces, we can traverse its combinatorial structure, isolate a level, answer incidence queries, and reason about how evenly a sample represents every halfplane. These ideas also explain why supersampling helps images and why it cannot eliminate every structured artifact.

A Point–Line Dictionary

We will use the affine convention

$$ p=(a,b) \quad\longleftrightarrow\quad p^\ast: y=ax-b, $$

and, conversely, the nonvertical line $\ell:y=mx-c$ maps to $\ell^\ast=(m,c)$. The minus sign is deliberate. It makes incidence symmetric:

$$ p\in\ell \iff b=ma-c \iff c=am-b \iff \ell^\ast\in p^\ast. $$

For example, $p=(2,3)$ maps to $p^\ast:y=2x-3$. The line $\ell:y=4x-5$ maps to $(4,5)$. Because $3=4(2)-5$, the primal point lies on the primal line; because $5=2(4)-3$, the dual point lies on the dual line.

The dictionary preserves incidence but reverses vertical order. At $x=m$, compare $p^\ast(m)=am-b$ with $c$, the height of $\ell^\ast=(m,c)$. Then

$$ p \text{ is above } \ell \iff b\gt ma-c \iff am-b\lt c \iff \ell^\ast \text{ is above } p^\ast. $$

There is an affine caveat: a vertical line $x=\alpha$ has no finite slope, so our formula gives it no ordinary dual point. Applications can rotate coordinates so no relevant line is vertical, handle vertical lines separately, or move to the projective plane. Projective duality treats directions as points at infinity: parallel affine lines meet there, and vertical lines are no longer exceptional. Homogeneous coordinates make this elegant, but production code must still choose a normalized representation and robust sign predicates.

From Lines to an Arrangement

An arrangement $\mathcal A(L)$ of lines is the subdivision induced by a set $L$. Its zero-dimensional cells are intersection vertices, its one-dimensional cells are maximal edge pieces between consecutive vertices on a line (including unbounded rays), and its two-dimensional cells are faces. The arrangement retains far more than the set of pairwise intersections: it records which edges bound which faces and the order of vertices along every line.

If $n$ lines are in general position—no two parallel and no three concurrent—there are

$$V=\binom n2,\qquad E=n^2,\qquad F=\frac{n(n+1)}2+1.$$

Thus all three totals are $O(n^2)$, and the bound is tight. A full explicit representation cannot be built faster than its quadratic output. A DCEL, introduced in Part 7, is a natural representation once unbounded cells are handled with an outer boundary convention or a projective/topological compactification.

Constructing and Traversing the Subdivision

A simple incremental construction starts with an empty arrangement and inserts lines one at a time. To insert $\ell$, intersect it with all previous lines, sort the intersections along $\ell$, split crossed edges, and connect the resulting pieces. With a DCEL, every split updates twins, next/prev links, origins, and incident faces. In general position, insertion $i$ creates $i-1$ vertices, $i$ new edges along $\ell$, and $i$ new faces.

Sorting from scratch on every insertion gives a straightforward $O(n^2\log n)$ implementation. More sophisticated topological sweeps construct an arrangement in optimal $O(n^2)$ time while maintaining only the combinatorial order of crossings. If an application needs only a zone—the faces and edges crossed by one new line—the zone theorem says its complexity is linear in $n$, even though the whole arrangement is quadratic.

Traversal is local. Along one input line, follow edge twins and endpoint incidence to visit intersections in order. Around a vertex, rotate through incident half-edges. Around a face, follow next. Across an edge, take its twin to the neighboring face. These operations support point location, walking between samples, and extracting order-defined chains such as levels.

from fractions import Fraction

def intersection(l1, l2):
    """Lines are y=m*x-c; return an exact point or None if parallel."""
    m1, c1 = l1
    m2, c2 = l2
    if m1 == m2:
        return None
    x = Fraction(c1 - c2, m1 - m2)
    return x, m1 * x - c1

def insertion_order(new_line, old_lines):
    """Crossings encountered from left to right on new_line."""
    hits = []
    for old_id, old_line in enumerate(old_lines):
        point = intersection(new_line, old_line)
        if point is not None:
            hits.append((point[0], point[1], old_id))
    hits.sort(key=lambda hit: (hit[0], hit[1], hit[2]))
    return hits

# A real builder now splits DCEL edges in this order. Fractions make
# intersections exact when input slopes and intercepts are integers.

Exact rationals avoid inconsistent vertex coordinates in this teaching implementation, though numerator growth can be expensive. A faster system commonly uses filtered arithmetic: approximate comparisons first, exact determinant signs when the result is uncertain.

Levels and the $k$-Level

At a point $q$ not on an arrangement line, its level is the number of lines strictly below it. Crossing a line upward increases the level by one; crossing downward decreases it by one. The $k$-level is the closure of arrangement edges having exactly $k$ lines below them. Depending on indexing, the lower envelope is level 0, and the median level is near $k=n/2$.

Sweep a vertical line from left to right. Between intersection events, the arrangement lines have a fixed bottom-to-top order. At a simple intersection, two adjacent lines swap. The edge occupying rank $k+1$ traces the $k$-level. This is a kinetic-order view of the same event logic developed in Part 6.

The combinatorial complexity of a $k$-level is a deep question: it can be far smaller than the entire arrangement, but tight general bounds are subtle. The algorithmic lesson is to distinguish “build everything, then select” from output-sensitive methods that follow only the desired rank boundary. Levels arise in regression estimators, depth measures, selection among linear functions, and dual formulations of point-line incidence problems.

Discrepancy, Halfplanes, and Supersampling

For a finite sample $P$ intended to represent a domain with measure $\mu$, range discrepancy asks how badly sample counts disagree with area over a family $\mathcal R$:

$$ D_{\mathcal R}(P)=\sup_{R\in\mathcal R} \left|\frac{|P\cap R|}{|P|}-\mu(R)\right|. $$

If $\mathcal R$ is the family of halfplanes, duality links the count $|P\cap R|$ to vertical order among dual lines. A boundary line becomes a query point; primal points on one side correspond to dual lines above or below it. Searching for a worst halfplane therefore becomes searching arrangement cells or levels where this count changes. Incidence events are exactly the arrangement vertices at which the ordering changes.

This gives a clean intuition for supersampling. A pixel value approximates an area integral by counting or weighting subpixel samples. A hard geometric edge clips the pixel with a halfplane locally, so low halfplane discrepancy means sample coverage tracks true covered area for every edge orientation and offset. A regular grid can be excellent for some edges yet align catastrophically with others; jittered, stratified, or low-discrepancy patterns trade perfect periodicity for more uniform range counts.

The analogy has limits. Real filters are weighted, footprints may be curved, and neighboring pixels share structure. More samples reduce integration error but do not repair an incorrect visibility test, inconsistent boundary convention, or aliasing above the reconstruction bandwidth. Duality tells us which counts matter; it does not make finite sampling exact.

Degeneracies Are Structural

General position simplifies formulas, not data. Parallel lines have no affine intersection and preserve their mutual order. Concurrent lines create one vertex of high degree instead of many pairwise vertices. Coincident lines represent duplicate constraints and induce overlapping one-dimensional geometry. Treating either case as many nearly separated events can corrupt topology.

A robust arrangement builder should therefore group equal event coordinates, classify parallel and coincident pairs before division, order all incident edges consistently, and state whether multiplicity matters to levels. Symbolic perturbation can impose a combinatorial order without moving coordinates numerically. Projective handling removes the special status of parallel directions, but coincident objects still require explicit multiplicity semantics.

What Duality Buys—and What Comes Next

Duality converts collinear primal points into concurrent dual lines, supporting incidence detection and line fitting; converts halfplane counts into above/below counts; and turns optimization over lines into envelope and level problems. Arrangements supply the map on which those transformed questions live. The useful habit is to ask whether exchanging points and hyperplanes changes an awkward geometric relation into an order relation.

Part 19 carries that habit into three dimensions. Convex hulls and half-space intersections become dual views, while paraboloid lifting turns planar Delaunay structure into a three-dimensional lower hull. The predicates grow more demanding, but the recurring strategy remains: choose a representation in which the desired combinatorics become visible.