Line Arrangements and Duality

Line Arrangements

An arrangement of lines $\mathcal{A}(\mathcal{L})$ is the subdivision of the plane induced by a set of $n$ lines $\mathcal{L}$. The arrangement consists of:

• Vertices: intersection points of lines. At most $\binom{n}{2}$ vertices
• Edges: maximal connected portions of lines between vertices. At most $n^2$ edges
• Faces: connected regions of $\mathbb{R}^2 \setminus \bigcup \mathcal{L}$. At most $\binom{n}{2} + n + 1$ faces

By Euler's formula for planar subdivisions: $V - E + F = 1$ (connected) or $2$ (if counting the unbounded face appropriately).

Complexity: $\Theta(n^2)$ for $n$ lines in general position (no two parallel, no three concurrent). This is tight.

Construction

Incremental algorithm: insert lines one at a time, updating the arrangement.

For each new line $\ell$:

1. Find a face of the current arrangement that $\ell$ enters
2. Walk along $\ell$ through the arrangement, splitting each traversed face into two
3. Each face traversal takes $O(1)$ amortized time

Total complexity: $O(n^2)$ time and space, which is optimal since the arrangement has $\Theta(n^2)$ features. The walk uses the zone of the new line.

DCEL Representation

Arrangements are typically stored as a doubly-connected edge list (DCEL):

• Each edge is split into two half-edges with opposite orientations
• Each half-edge stores: origin vertex, twin half-edge, incident face, next/prev half-edge in face boundary
• Supports $O(1)$ local navigation (adjacent faces, edges around a vertex)

Zone Theorem

The zone of a line $\ell$ in an arrangement of $n$ lines is the set of faces whose closure intersects $\ell$.

Zone theorem: the total complexity (number of edges bounding faces) of the zone of any line in an arrangement of $n$ lines is $O(n)$.

Proof sketch: charge each edge in the zone to one of the $n$ lines. A careful argument shows each line contributes $O(1)$ edges to the zone, giving $O(n)$ total.

Consequences:

• Inserting a new line into an arrangement takes $O(n)$ time (traverse its zone)
• Incremental construction: $\sum_{i=1}^n O(i) = O(n^2)$, matching the output size
• The zone theorem generalizes to hyperplane arrangements in $\mathbb{R}^d$: zone complexity is $O(n^{d-1})$

Point-Line Duality

A fundamental transform mapping points to lines and vice versa. Standard duality:

$\text{Point } p = (a, b) \quad \longleftrightarrow \quad \text{Line } p^* : y = ax - b$

$\text{Line } \ell : y = cx - d \quad \longleftrightarrow \quad \text{Point } \ell^* = (c, d)$

Key property (incidence preservation): point $p$ lies on line $\ell$ iff point $\ell^*$ lies on line $p^*$. More specifically:

• $p$ is above $\ell$ iff $\ell^*$ is above $p^*$
• $p$ is below $\ell$ iff $\ell^*$ is below $p^*$

Order preservation: the duality preserves the vertical ordering relation.

Primal-Dual Correspondences

| Primal | Dual | |---|---| | Point | Line | | Line | Point | | Point above line | Dual line above dual point | | Line through two points | Point = intersection of two dual lines | | Convex hull vertex | Line bounding dual arrangement face | | Upper envelope of lines | Convex hull of dual points |

Applications of Duality

1. Ham-sandwich cuts via duality: transformed to finding a point in an arrangement with specific level properties
2. Minimum area triangle: three points from a set $S$ forming the minimum area triangle. Via duality, this relates to closest lines in the dual arrangement
3. Slope selection: find the $k$-th smallest slope among all $\binom{n}{2}$ point pairs. Via duality, this becomes a $k$-level problem. $O(n \log n)$ algorithm via parametric search or Cole's method
4. Linear programming: the dual of finding the lowest point above $n$ lines is finding the intersection point of lines below $n$ dual points

Levels in Arrangements

The $k$-level of an arrangement of lines is the set of points that have exactly $k$ lines strictly below them. Equivalently, it is a piecewise-linear $x$-monotone curve.

• Level 0 = lower envelope; level $n$ = upper envelope
• Complexity of the $k$-level: at most $O(n \sqrt{k+1})$ (Dey, 1998). Best lower bound: $n \cdot 2^{\Omega(\sqrt{\log n})}$ (Toth). Exact complexity is a major open problem
• The $\leq k$-level (all points with $\leq k$ lines below) has complexity $O(nk)$

Upper and Lower Envelopes

The upper envelope of $n$ lines: the pointwise maximum $\max_i (a_i x + b_i)$.

• Complexity: $O(n)$ segments (each line contributes at most one segment)
• Computation: $O(n \log n)$ via divide-and-conquer or incremental insertion
• Equivalent to the convex hull of the dual point set (upper hull)

For curves (not lines): the upper envelope of $n$ curves that pairwise intersect at most $s$ times has complexity $\lambda_s(n)$, a slowly growing function related to Davenport-Schinzel sequences:

• $s = 1$: $\lambda_1(n) = n$ (lines)
• $s = 2$: $\lambda_2(n) = 2n - 1$ (line segments)
• $s = 3$: $\lambda_3(n) = \Theta(n \alpha(n))$ where $\alpha$ is the inverse Ackermann function

Ham-Sandwich Theorem

Theorem (Stone-Tukey): given $d$ finite Borel measures in $\mathbb{R}^d$, there exists a hyperplane that simultaneously bisects all $d$ measures.

In $\mathbb{R}^2$: given two point sets (red and blue), there exists a line that bisects both. Proof uses the intermediate value theorem or Borsuk-Ulam theorem.

Algorithm in $\mathbb{R}^2$: $O(n \log n)$ via duality. Transform to finding a point at a specific level in the dual arrangement.

Discrete version: for $n$ red and $n$ blue points in general position, a ham-sandwich cut exists. Not unique in general; the space of valid cuts has specific structure.

Helly's Theorem

Theorem (Helly, 1923): let $\mathcal{C} = \{C_1, \ldots, C_n\}$ be a finite collection of convex sets in $\mathbb{R}^d$ with $n > d$. If every $d+1$ of them have a common point, then all of them have a common point.

$\bigcap_{i=1}^n C_i \neq \emptyset \iff \text{every } (d+1)\text{-subset has non-empty intersection}$

In $\mathbb{R}^2$: if every three convex sets have a common point, then they all do.

Applications:

• Halfplane intersection: $n$ halfplanes have a common point iff every 3 do. Reduces feasibility of LP to checking $O(n^3)$ triples (not efficient, but theoretically fundamental)
• Helly dimension: generalizes to abstract convexity spaces
• Fractional Helly theorem (Barany, 1982): if at least $\alpha \binom{n}{d+1}$ of the $(d+1)$-subsets have non-empty intersection (for $\alpha > 0$), then at least $\beta n$ of the sets have a common point, where $\beta = 1 - (1-\alpha)^{1/(d+1)}$

Radon's Theorem

Theorem (Radon, 1921): any $d + 2$ points in $\mathbb{R}^d$ can be partitioned into two sets whose convex hulls intersect.

In $\mathbb{R}^2$: any 4 points can be partitioned into two pairs whose convex hulls (line segments) intersect. Equivalently, one point is inside the triangle of the other three, or the two diagonals of the quadrilateral cross.

Radon partition: the partition $S = S_1 \cup S_2$ with $\text{conv}(S_1) \cap \text{conv}(S_2) \neq \emptyset$. Can be computed by finding a non-trivial affine dependence among the points.

Radon's theorem implies Helly's theorem (classical proof by induction).

Hyperplane Arrangements

In $\mathbb{R}^d$, an arrangement of $n$ hyperplanes has:

• At most $\binom{n}{d}$ vertices
• Total complexity $O(n^d)$ (faces of all dimensions)
• Can be constructed incrementally in $O(n^d)$ time (optimal)

Number of faces: the number of regions (full-dimensional faces) is at most $\sum_{k=0}^d \binom{n}{k}$, which is $\Theta(n^d)$ in general position. This is the Zaslavsky formula (computable via the characteristic polynomial of the intersection lattice).

Applications:

• Configuration spaces: robot arm reachability
• Machine learning: hyperplane arrangements partition feature space into regions with different linear functions (ReLU networks, decision trees)
• Discrete geometry: many counting problems reduce to arrangement complexity

Arrangement of Segments

For $n$ line segments with $k$ intersection points:

• Output complexity: $O(n + k)$
• Construction: Bentley-Ottmann sweep gives $O((n + k) \log n)$ (see Chapter 07)
• Bounding $k$: at most $\binom{n}{2}$, but often much smaller in practice

Applications and Connections

• Linear programming: the optimal LP solution is a vertex of the arrangement of constraint hyperplanes. Dual LP corresponds to envelope computation
• Geometric optimization: many problems (smallest enclosing circle, widest corridor) reduce to computations in line arrangements
• Machine learning: SVM margins correspond to distances between arrangement features; ReLU network decision boundaries are hyperplane arrangements
• Discrete and combinatorial geometry: Szemeredi-Trotter theorem bounds point-line incidences to $O(n^{2/3}m^{2/3} + n + m)$, with deep consequences for arrangement complexity and additive combinatorics