Geometric Duality

Take three points on a piece of paper. Draw the unique line through each pair. Most of the time those three lines form a triangle — each pair meets at a different corner. But if the three original points happen to be collinear (all on one line), something special occurs: the three lines you draw all pass through a single point. Collinearity on one side, concurrence on the other.

That symmetry is not a coincidence. It is the fingerprint of geometric duality — a precise, reversible transformation that swaps every point for a line and every line for a point, turning every statement about collinear points into an equivalent statement about concurrent lines.

Duality has been studied since the early 19th century by mathematicians such as Jean-Victor Poncelet and Joseph Diez Gergonne, who noticed that in projective geometry, points and lines play perfectly symmetric roles. Strip away coordinates and you are left with a beautiful two-way mirror: every true theorem about points spawns a twin theorem about lines, for free.

Modern algorithm designers use duality as a practical tool: hard questions about point arrangements often become easy questions about line arrangements, or vice versa. The convex hull of a point set, for example, is intimately linked to the lower envelope of the dual lines — swap the picture and a different algorithm becomes obvious.

Click anywhere on the canvas to place a point. Its dual line appears instantly, drawn using the standard duality map $p = (a, b) \mapsto \ell\colon y = ax - b$. Drag existing points to move them.

<!-- {{c_html_comment}} -->
<p class="hint">{{hint_para}}</p>
<div class="canvas-wrap">
  <canvas id="cv" width="480" height="300"></canvas>
  <p class="canvas-label">{{canvas_label}}</p>
</div>
<div class="status" id="status"></div>
<div class="btns">
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  <button id="btn-example" type="button">{{btn_example}}</button>
</div>

/* {{c_css_comment}} */
* { 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-wrap { position: relative; display: inline-block; width: 100%; }
canvas { display: block; width: 100%; max-width: 480px; height: auto;
         border: 1px solid #cdd9e3; border-radius: 8px; cursor: crosshair; background: #f8fafb; }
.canvas-label { font-size: .78rem; color: #888; margin: .3rem 0 0; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin: .4rem 0; }
.status.collinear { color: #0a7d33; }
.status.normal { color: #1d3557; }
.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; }

// Code not found

Watch what happens when three points become collinear (the blue alignment guide appears). Their three dual lines will converge at a single point — concurrence as a direct consequence of collinearity. Move a point off the line and the three dual lines spread back into a triangle of intersections.

The demo highlights the dual intersection point whenever the three lines are concurrent, letting you see the duality in both directions at once.

Duality itself is wonderfully cheap. The standard map for a point $p = (a, b)$ with $b \neq 0$ is:

$$p = (a,\, b) \;\longleftrightarrow\; \ell\colon y = ax - b$$

Apply it twice and you are back where you started — the map is its own inverse. Computing the dual of $n$ points costs $O(n)$ time and $O(n)$ space. Nothing hard there.

The power — and the hardness — emerges when you ask questions about the arrangement the dual lines carve out:

• The zone theorem: the total complexity of the cells that a new line $\ell$ crosses in an arrangement of $n$ lines is $O(n)$. This well-known result (proved by Edelsbrunner, Guibas, and Sharir in 1986) is the engine behind efficient incremental algorithms.
• Levels in arrangements: the $k$-th level of an arrangement of $n$ lines — the chain of edges with exactly $k$ lines below them — has complexity $O(n \cdot k^{1/3})$ (best known upper bound). Determining the exact tight bound is a longstanding open problem.
• Ham-sandwich theorem: given $d$ finite point sets in $\mathbb{R}^d$, there exists a hyperplane bisecting all of them simultaneously. In the plane this is solved in $O(n \log n)$ via duality, but in higher dimensions the algorithmic complexity is an active research topic.
• Counting intersections: counting all $\binom{n}{2}$ pairwise intersections of $n$ dual lines takes $O(n^2)$, which matches the output size — optimal but large. Counting only intersections inside a query region is harder.

Duality does not make hard problems easy; it re-labels them. Sometimes the re-labeling lands you in a known tractable case; sometimes it reveals that the difficulty was always there, just wearing a different face. Compare this with the situation in linear programming, where projecting a high-dimensional polytope onto a lower-dimensional one can make a feasibility question suddenly visible — or with convex hull computation, where the duality between upper hulls and lower envelopes is explicit in the algorithm.

Duality is one of the most reused ideas in all of computational geometry:

• Voronoi diagrams and Delaunay triangulations: the Delaunay triangulation of a point set is the straight-line dual graph of its Voronoi diagram. Algorithms that build one often implicitly build the other. These structures underpin mesh generation, interpolation, and geographic information systems.
• Halfplane range searching: "which points lie in a query halfplane?" dualizes to "which dual lines pass above a query point?" — turning a geometric containment question into a line arrangement query.
• Smallest enclosing circle: the center of the smallest circle enclosing $n$ points lies on the Delaunay triangulation, and duality shortcuts the proof.
• Art gallery and visibility problems: dual arrangements of lines encode all possible sightlines in a polygon, directly connecting to convex hull theory.
• Machine learning – support vector machines: the hard-margin SVM finds a separating hyperplane; the dual optimization problem is a quadratic program over Lagrange multipliers, and the support vectors are exactly the dual witness points. Duality here is algebraic rather than geometric, but the conceptual leap is the same.

Whenever a problem asks "do these objects intersect?" or "does this point lie inside that region?", there is a good chance that flipping to the dual picture will expose a simpler structure — or at least a different algorithm worth trying.

Duality is one of those ideas that feels almost too good to be true: press a button, swap points and lines, and the diagram you were struggling with becomes obvious from the other side. Three collinear points become three concurrent lines — not by accident, but because the transformation preserves every incidence relationship perfectly.

The trick costs nothing ($O(n)$ time) and generalizes far beyond the plane — to higher dimensions, to spheres, to the algebraic setting of linear programming. It connects convex hull algorithms to line-arrangement sweeps, and Voronoi diagrams to Delaunay triangulations.

The next time geometry feels stuck, try asking: what does the dual look like? The answer might be a theorem you already know, just wearing a different face.