Line Arrangements

Take a blank plane and draw a line. It splits the plane into two half-planes. Draw a second line that crosses the first — now you have four regions, two intersection points and four rays. Keep adding lines. Every new one slices through existing regions, creating fresh edges and vertices as it goes.

This structure — all the cells, edges and vertices produced by $n$ lines — is called an arrangement of lines. Arrangements sit at the heart of computational geometry: they appear whenever an algorithm needs to reason about all possible intersections, half-planes or dual transforms at once.

The key question is not just how many objects are created in total, but how much that count grows when you add one more line. That incremental cost is bounded by the Zone Theorem, a clean and powerful result that underlies many efficient geometry algorithms.

Click Add line to insert a new line in general position and watch the plane shatter into more and more pieces. The counters at the bottom show the exact number of vertices $V$, edges $E$ and faces $F$ (bounded regions plus the one unbounded face) after each step.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<canvas id="canvas" width="420" height="260"></canvas>
<div class="stats" id="stats">
  <span><b>n</b> = <span id="n">0</span></span>
  <span><b>V</b> = <span id="V">0</span></span>
  <span><b>E</b> = <span id="E">0</span></span>
  <span><b>F</b> = <span id="F">1</span></span>
</div>
<div class="formulas" id="formulas">{{formula_label}}</div>
<div class="btns">
  <button id="addLine" type="button">{{btn_add}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px;
         background: #f7f9fb; width: 100%; max-width: 420px; height: auto; }
.stats { display: flex; gap: 1.2rem; font-size: .95rem; margin: .5rem 0 .2rem;
         flex-wrap: wrap; }
.formulas { font-size: .82rem; color: #5a6a7a; margin: 0 0 .5rem;
            font-style: italic; min-height: 1.2em; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .3rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Notice that each new line crosses all previous lines, contributing exactly $k$ new vertices, $k+1$ new edges and $k$ new bounded-region splits when it is the $k$-th line added ($k$ starts at 0). That bounded growth per step is exactly what the Zone Theorem formalizes.

With $n$ lines in general position (no two parallel, no three concurrent) the exact counts are:

• Vertices: $\binom{n}{2} = \frac{n(n-1)}{2}$
• Edges: $n^2$
• Faces (bounded + unbounded): $\binom{n}{2} + n + 1 = \frac{n^2+n+2}{2}$

These grow as $\Theta(n^2)$, so a full arrangement has quadratic complexity. The deeper question is: can you build one incrementally without doing more than $O(n^2)$ total work?

The answer is yes, and the key is the Zone Theorem (Edelsbrunner, Guibas, Sharir, 1986):

The total complexity of the zone of a line $\ell$ in an arrangement of $n$ lines — that is, all faces whose closure intersects $\ell$ — is $O(n)$.

This means inserting $\ell$ as the $(n+1)$-th line only requires touching $O(n)$ faces, edges and vertices. Summing over all insertions gives $O(n^2)$ total — matching the output size, so the algorithm is optimal.

The proof is a clever charging argument: orient $\ell$ left-to-right and charge each face in its zone to the edge where $\ell$ first crosses into it. Each edge can be charged at most a constant number of times, giving the linear bound per line.

Compare this to the halting problem: there the difficulty is undecidability. Here everything is decidable and efficiently computable — the challenge is just proving the tight $O(n)$ per-step bound to avoid accidentally doing $O(n^2)$ per step, which would give $O(n^3)$ total.

Arrangements of lines (and their higher-dimensional cousins, arrangements of hyperplanes) are a foundational data structure in computational geometry:

• Half-plane intersection: the feasible region of a 2-D linear program is the intersection of $n$ half-planes — computing it incrementally with the Zone Theorem takes $O(n \log n)$ time.
• Point location: precomputing an arrangement lets you answer "which face contains this query point?" in $O(\log n)$ time after $O(n^2)$ preprocessing.
• Ham-sandwich cuts: the dual transform converts a point set into lines, and a ham-sandwich cut becomes a median-level computation in the arrangement.
• Motion planning: a robot moving among line obstacles must reason about arrangements of constraint lines in configuration space.
• Topological sweep: algorithms that sweep through an arrangement in topological order use Zone-Theorem arguments to prove $O(n^2)$ total work without physically moving a sweep line.

Whenever a geometry problem touches "all pairs of lines" or "all half-plane constraints at once," you are likely working inside an arrangement. The Zone Theorem is what keeps that work tractable. See also max flow for another setting where tight combinatorial bounds drive algorithm design.

$n$ lines in general position carve the plane into a structure of exactly $\Theta(n^2)$ pieces — vertices, edges and faces that all grow together at the same quadratic rate. That is inevitable: each pair of lines meets exactly once, and every meeting point is a vertex.

What is not obvious is that you can build this structure one line at a time, each step costing only $O(n)$ work. That is the Zone Theorem — and it is the reason a full arrangement can be constructed in $O(n^2)$ time, matching the output size with no wasted effort.

The next time you see a geometry algorithm that handles $n$ constraints by considering all pairs, look for the arrangement hiding underneath — and the Zone Theorem holding it together.