Introduction

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.

Try It

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

<!-- Geometric duality demo: points in the plane dual to lines y=ax-b -->
<p class="hint">Click on the canvas to place up to 5 points. Each point <b>P = (a, b)</b> maps to the dual line <b>y = ax − b</b>. When 3 points are <b>collinear</b>, their 3 dual lines become <b>concurrent</b> (orange dot). Drag points to explore.</p>
<div class="canvas-wrap">
  <canvas id="cv" width="480" height="300"></canvas>
  <p class="canvas-label">Point space — click to place points; their dual lines are drawn in the same view</p>
</div>
<div class="status" id="status"></div>
<div class="btns">
  <button id="btn-reset" type="button" class="ghost">Clear all</button>
  <button id="btn-example" type="button">Load collinear example</button>
</div>

/* Layout for the duality demo canvas and controls */
* { 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; }

// Geometric Duality interactive demo
// Standard point-line duality: point P=(a,b) dualizes to line y=ax-b
// Collinear points produce concurrent dual lines — the core duality theorem
const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
const W = 480, H = 300;
// Canvas coordinate system: origin at center, y-axis up, scaled by SCALE px per unit
const CX = W / 2, CY = H / 2, SCALE = 60;

// Array of world-space points [a, b]; dragging index
let points = [];
let dragging = null;

// Convert between canvas pixels and world coordinates
function toWorld(px, py) { return [(px - CX) / SCALE, -(py - CY) / SCALE]; }
function toCanvas(wx, wy) { return [CX + wx * SCALE, CY - wy * SCALE]; }

// Evaluate the dual line y=ax-b at a given x
// The standard duality map: point (a,b) <-> line y=ax-b
function dualLineY(wx, a, b) { return a * wx - b; }

// Return canvas endpoints for the dual line of point (a,b) clipped to canvas width
function clipLine(a, b) {
  const x0 = (0 - CX) / SCALE, x1 = (W - CX) / SCALE;
  const [cx0, cy0] = toCanvas(x0, dualLineY(x0, a, b));
  const [cx1, cy1] = toCanvas(x1, dualLineY(x1, a, b));
  return [cx0, cy0, cx1, cy1];
}

// Return true when the first 3 points are collinear (cross-product area near zero)
function areCollinear(pts) {
  if (pts.length < 3) return false;
  const [ax, ay] = pts[0], [bx, by] = pts[1], [cx, cy] = pts[2];
  return Math.abs((bx - ax) * (cy - ay) - (cx - ax) * (by - ay)) < 0.04;
}

// Compute intersection of two dual lines y=a1*x-b1 and y=a2*x-b2
// Solving a1*x-b1 = a2*x-b2 gives x=(b1-b2)/(a1-a2)
// Note: numerator is b1-b2, not b2-b1
function dualIntersection(p1, p2) {
  const [a1, b1] = p1, [a2, b2] = p2;
  if (Math.abs(a1 - a2) < 1e-9) return null;
  const x = (b1 - b2) / (a1 - a2);
  const y = dualLineY(x, a1, b1);
  return [x, y];
}

// Return the single concurrent point of the first 3 dual lines, or null if they do not meet
function getConcurrentPoint(pts) {
  if (pts.length < 3) return null;
  const i01 = dualIntersection(pts[0], pts[1]);
  const i02 = dualIntersection(pts[0], pts[2]);
  const i12 = dualIntersection(pts[1], pts[2]);
  const valid = [i01, i02, i12].filter(Boolean);
  if (valid.length < 2) return null;
  const [x0, y0] = valid[0];
  const scale = Math.max(1, Math.abs(x0), Math.abs(y0));
  const EPS = 0.02;
  const allClose = valid.every(([x, y]) =>
    Math.abs(x - x0) / scale < EPS && Math.abs(y - y0) / scale < EPS
  );
  return allClose ? valid[0] : null;
}

// Draw the x and y axes as faint grid lines
function drawAxes() {
  ctx.save();
  ctx.strokeStyle = '#d0d8e0';
  ctx.lineWidth = 1;
  ctx.beginPath(); ctx.moveTo(0, CY); ctx.lineTo(W, CY); ctx.stroke();
  ctx.beginPath(); ctx.moveTo(CX, 0); ctx.lineTo(CX, H); ctx.stroke();
  ctx.restore();
}

// Main render function: clear, axes, dual lines, concurrent dot, primal points, status
function draw() {
  ctx.clearRect(0, 0, W, H);
  drawAxes();

  const collinear = areCollinear(points);
  const concurrentPt = (points.length >= 3) ? getConcurrentPoint(points.slice(0, 3)) : null;

  // Draw each dual line across the full canvas width
  const COLORS = ['#e63946', '#2196f3', '#ff9800', '#9c27b0', '#00897b'];
  points.forEach(([a, b], i) => {
    const [cx0, cy0, cx1, cy1] = clipLine(a, b);
    ctx.save();
    ctx.strokeStyle = COLORS[i % COLORS.length];
    ctx.lineWidth = 1.8;
    ctx.globalAlpha = 0.7;
    ctx.beginPath(); ctx.moveTo(cx0, cy0); ctx.lineTo(cx1, cy1); ctx.stroke();
    ctx.restore();
  });

  // Draw an orange circle at the concurrent intersection when collinear
  if (concurrentPt) {
    const [cx, cy] = toCanvas(concurrentPt[0], concurrentPt[1]);
    if (cx >= 0 && cx <= W && cy >= 0 && cy <= H) {
      ctx.save();
      ctx.fillStyle = '#ff9800';
      ctx.strokeStyle = '#333';
      ctx.lineWidth = 1.5;
      ctx.beginPath();
      ctx.arc(cx, cy, 7, 0, 2 * Math.PI);
      ctx.fill(); ctx.stroke();
      ctx.restore();
    }
  }

  // Draw the primal points on top with labels P1, P2, ...
  points.forEach(([a, b], i) => {
    const [px, py] = toCanvas(a, b);
    ctx.save();
    ctx.fillStyle = COLORS[i % COLORS.length];
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 2;
    ctx.beginPath(); ctx.arc(px, py, 7, 0, 2 * Math.PI);
    ctx.fill(); ctx.stroke();
    ctx.fillStyle = '#222';
    ctx.font = 'bold 11px system-ui';
    ctx.fillText('P' + (i + 1), px + 9, py - 5);
    ctx.restore();
  });

  // Update the status bar text and color class
  const statusEl = document.getElementById('status');
  if (points.length === 0) {
    statusEl.textContent = 'Click to place a point.';
    statusEl.className = 'status normal';
  } else if (points.length < 3) {
    statusEl.textContent = 'Place at least 3 points to see the duality in action.';
    statusEl.className = 'status normal';
  } else if (collinear) {
    statusEl.textContent = '✓ Points are collinear → dual lines are concurrent! (orange dot)';
    statusEl.className = 'status collinear';
  } else {
    statusEl.textContent = 'Points are in general position — dual lines form a triangle of intersections.';
    statusEl.className = 'status normal';
  }
}

// Return the index of a point under the cursor, or -1 if none
function hitTest(ex, ey) {
  const rect = cv.getBoundingClientRect();
  const scaleX = W / rect.width, scaleY = H / rect.height;
  const px = (ex - rect.left) * scaleX;
  const py = (ey - rect.top) * scaleY;
  for (let i = 0; i < points.length; i++) {
    const [a, b] = points[i];
    const [cpx, cpy] = toCanvas(a, b);
    const dx = px - cpx, dy = py - cpy;
    if (dx * dx + dy * dy < 100) return i;
  }
  return -1;
}

cv.addEventListener('mousedown', e => {
  const idx = hitTest(e.clientX, e.clientY);
  if (idx >= 0) { dragging = idx; return; }
  if (points.length >= 5) return;
  const rect = cv.getBoundingClientRect();
  const scaleX = W / rect.width, scaleY = H / rect.height;
  const px = (e.clientX - rect.left) * scaleX;
  const py = (e.clientY - rect.top) * scaleY;
  points.push(toWorld(px, py));
  draw();
});

cv.addEventListener('mousemove', e => {
  if (dragging === null) return;
  const rect = cv.getBoundingClientRect();
  const scaleX = W / rect.width, scaleY = H / rect.height;
  const px = (e.clientX - rect.left) * scaleX;
  const py = (e.clientY - rect.top) * scaleY;
  points[dragging] = toWorld(px, py);
  draw();
});

cv.addEventListener('mouseup', () => { dragging = null; });
cv.addEventListener('mouseleave', () => { dragging = null; });

// Touch event support for mobile devices
cv.addEventListener('touchstart', e => {
  e.preventDefault();
  const t = e.touches[0];
  const idx = hitTest(t.clientX, t.clientY);
  if (idx >= 0) { dragging = idx; return; }
  if (points.length >= 5) return;
  const rect = cv.getBoundingClientRect();
  const scaleX = W / rect.width, scaleY = H / rect.height;
  const px = (t.clientX - rect.left) * scaleX;
  const py = (t.clientY - rect.top) * scaleY;
  points.push(toWorld(px, py));
  draw();
}, { passive: false });

cv.addEventListener('touchmove', e => {
  e.preventDefault();
  if (dragging === null) return;
  const t = e.touches[0];
  const rect = cv.getBoundingClientRect();
  const scaleX = W / rect.width, scaleY = H / rect.height;
  const px = (t.clientX - rect.left) * scaleX;
  const py = (t.clientY - rect.top) * scaleY;
  points[dragging] = toWorld(px, py);
  draw();
}, { passive: false });

cv.addEventListener('touchend', () => { dragging = null; });

document.getElementById('btn-reset').addEventListener('click', () => { points = []; draw(); });

// Load a preset collinear configuration to demonstrate duality
document.getElementById('btn-example').addEventListener('click', () => {
  // Three points on y=-1 are collinear; their dual lines y=ax+1 all pass through (0,1)
  points = [[-2, -1], [0, -1], [2, -1]];
  draw();
});

draw();
Result
Console

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.

The Real Complexity

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

p=(a, b)  ⟷  ℓ ⁣:y=ax−bp = (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 nn points costs O(n)O(n) time and O(n)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 nn lines is O(n)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 kk-th level of an arrangement of nn lines — the chain of edges with exactly kk lines below them — has complexity O(n⋅k1/3)O(n \cdot k^{1/3}) (best known upper bound). Determining the exact tight bound is a longstanding open problem.
  • Ham-sandwich theorem: given dd finite point sets in Rd\mathbb{R}^d, there exists a hyperplane bisecting all of them simultaneously. In the plane this is solved in O(nlog⁡n)O(n \log n) via duality, but in higher dimensions the algorithmic complexity is an active research topic.
  • Counting intersections: counting all (n2)\binom{n}{2} pairwise intersections of nn dual lines takes O(n2)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.

Where It Matters

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 nn 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.

Conclusion

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)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/geometric-duality/Content licensed under CC BY-NC 4.0.