Half-Plane Intersection

Every linear inequality you have ever written down — $ax + by \le c$ — draws a straight line across the plane and keeps everything on one side of it. That surviving side is a half-plane: an infinite region bounded by one straight edge.

Now stack up many of these constraints at once. A factory that needs $2x + y \le 40$ of labor, $x + 3y \le 30$ of material, and $x, y \ge 0$ of common sense is really asking: where do all these half-planes overlap? The answer is always a single convex region — possibly empty, possibly unbounded, but never with a dent in it.

That region is the feasible set behind every linear program. The question this article asks is simple: given $n$ half-planes, how fast can you actually compute the shape of their intersection?

Start with a big bounding square — the "universe" before any constraint is applied. Every time you add a half-plane, the polygon gets clipped against it.

<p class="hint">{{hint_para}}</p>
<svg id="canvas" class="canvas" viewBox="0 0 300 300"></svg>
<div class="status" id="status">{{status_start}}</div>
<div class="btns">
  <button id="add" type="button">{{btn_add}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.canvas { width: 100%; max-width: 300px; height: 260px; background: #f4f6f8; border: 1px solid #cdd9e3;
           border-radius: 8px; display: block; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
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: .5; cursor: default; }

// Code not found

Click Add constraint to throw in a fresh random half-plane; the demo clips the current polygon against it edge by edge, in the same way the sweep does it for real. Click Reset to start over from the full square. Watch how the region only ever shrinks and stays convex — it can never grow a notch or split in two.

The naive approach clips the current polygon against each new half-plane, one at a time. Clipping a polygon with $k$ edges against one half-plane costs $O(k)$, and after $n$ constraints the polygon can have up to $O(n)$ edges — so the total cost of adding them in an arbitrary order is $O(n^2)$ in the worst case.

The fix is to stop adding constraints in a random order. Every half-plane's boundary line has a direction: sort the $n$ half-planes by the angle of that boundary (an $O(n \log n)$ sort), then sweep through them in angular order, maintaining the current intersection as a deque of edges. Because consecutive half-planes in angle order interact predictably with the growing hull, each half-plane gets pushed and popped from the deque at most once — so the whole sweep after the sort is only $O(n)$.

• Sort by angle: $O(n \log n)$, dominates the whole algorithm.
• Deque sweep: each half-plane inserted once, popped at most a constant number of times — amortized $O(1)$ per half-plane.
• Total: $O(n \log n)$, matching the lower bound for the problem (you must at least sort, since the output edges appear in angular order around the region).

This is the same "sort first, then sweep linearly" pattern that powers convex hull algorithms — angular order is doing the heavy lifting in both.

Any time a system is described by "all of these linear limits must hold simultaneously," you are looking at a half-plane intersection in disguise:

• Linear programming: the feasible region of an LP is exactly the intersection of its constraint half-planes (in 2D) or half-spaces (in higher dimensions); the optimum sits at one of its corners.
• Robot motion and visibility: computing the region a robot can safely occupy, or the area visible from a point among straight obstacles, reduces to intersecting half-planes.
• Kinetic and dynamic geometry: as constraints move over time, maintaining their intersection incrementally is a core building block for real-time planning.
• Computer graphics: clipping a polygon against a viewing frustum or a clip window is literally intersecting it with a handful of half-planes.

Learn this one sweep and you have the mechanism behind the corner of every linear program and the silhouette behind every convex clipping window.

Half-plane intersection looks, at first glance, like it should cost you $O(n^2)$: clip a growing polygon against $n$ constraints, one at a time, and the edges pile up. But order the half-planes by the angle of their boundary first, sweep once with a deque, and the whole computation collapses to $O(n \log n)$ — as fast as sorting itself.

It is a small, elegant reminder that in computational geometry the hard part is rarely the geometry: it is finding the right order to process things in. Get the order right, and a quadratic-looking problem turns linearithmic — the same trick that makes convex hull construction fast.