Linear Programming in Linear Time

Linear programming (LP) is one of the most useful tools in all of optimization: given a set of linear inequalities and a linear objective, find the point that satisfies all the constraints and maximizes (or minimizes) the goal. It models everything from factory schedules to diet plans.

The general LP problem with n constraints and d variables was long known to be solvable in polynomial time — the simplex method is fast in practice, and the ellipsoid method proved polynomial complexity in 1979. But could small-dimensional LP be dramatically faster?

In 1984, Nimrod Megiddo answered yes. His prune-and-search algorithm solves LP in the plane — n linear constraints, objective along a line — in $O(n)$ time. No other approach had cracked the linear barrier for LP. The result was one of the first to show that the hard cases of polynomial-time problems can sometimes collapse to linear time when the dimension is held fixed.

The idea is elegant: instead of testing the optimum directly, pair up constraints, use each pair to prune half of the remaining candidates in constant time, and recurse on the surviving half. Each level of recursion halves the problem, so only $O(\log n)$ levels are needed — each costing $O(n)$ — giving $O(n)$ total after a careful implementation.

Below is a 2D linear programming instance: maximize cx (i.e. move as far right as possible) subject to n half-plane constraints of the form ax + by ≤ c. The feasible region is the intersection of all half-planes; the optimum is the rightmost feasible point.

<div id="controls">
  <button id="btnStep" type="button">{{btn_step}}</button>
  <button id="btnSolve" type="button">{{btn_solve}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
  <span id="info">n = <b id="nCount">0</b> {{info_constraints}}</span>
</div>
<canvas id="canvas" width="560" height="310"></canvas>
<div id="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; background: #f7f9fb; }
#controls { display: flex; gap: .5rem; align-items: center; flex-wrap: wrap; padding: .5rem .5rem .3rem; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border-radius: 7px; cursor: pointer;
         border: 1px solid #1d3557; background: #1d3557; color: #fff; }
button.ghost { background: #fff; color: #1d3557; }
#info { font-size: .85rem; color: #555; margin-left: .3rem; }
canvas { display: block; width: 100%; max-width: 560px; height: auto; border: 1px solid #cdd5de;
         border-radius: 8px; background: #fff; margin: 0 auto; }
#log { font-size: .8rem; color: #555; min-height: 1.6em; padding: .3rem .5rem; text-align: center; }

// Code not found

Press Step to watch the prune-and-search strategy eliminate constraints one batch at a time. Notice how each step cuts the active constraint count roughly in half — that halving is the heart of the $O(n)$ guarantee. Press Solve instantly to jump straight to the optimum, or Reset to start over with a new random instance.

How fast can you solve LP in two dimensions? Megiddo's answer is surprising even today.

• The naive bound is $O(n^{2})$: try all $O(n^{2})$ vertices of the constraint polytope and pick the best. Faster approaches reduced this, but not to linear.
• Megiddo's key insight (1984): pair up the n constraints arbitrarily. For each pair, compute a pivot value — the x-coordinate at which one constraint "takes over" from the other in limiting the objective. These $O(n)$ pivot values can be median-found in $O(n)$ time. Then determine (in $O(n)$ time) whether the optimum lies to the left or right of the median pivot; this single decision lets you discard at least n/4 constraints as permanently non-binding in any direction. Recurse.
• Recurrence: T(n) = T(3n/4) + $O(n)$, which solves to T(n) = $O(n)$ — linear time.
• Extension to d fixed dimensions: the same prune-and-search idea extends to any fixed d, giving $O(n)$ with the constant depending exponentially on d. For d = 3 Megiddo proved $O(n)$ as well; Seidel later gave a randomized $O(d! \cdot n)$ algorithm, and Clarkson an expected $O(d^{2}n)$ one.
• Status: LP in fixed dimension is solved — $O(n)$ is a lower bound too (you must read all constraints), so Megiddo's result is optimal in dimension 2 and 3. In high dimension the best deterministic bound is still super-linear and the precise complexity remains open.

The result also inspired the broader prune-and-search paradigm, used today across computational geometry for problems like smallest enclosing balls, ham-sandwich cuts, and weighted median finding. See also linear programming and selection and median finding.

Linear time LP in low dimensions is not just a theoretical prize — it changes what is feasible in practice:

• Computational geometry: smallest enclosing disk/ball, halfspace intersection, linear separability, and ham-sandwich cuts all reduce to low-dimensional LP and benefit directly from $O(n)$ algorithms.
• Robot motion planning: collision avoidance with convex obstacles in 2D or 3D reduces to linear programs with a bounded number of variables, making real-time guarantees achievable.
• Embedded and real-time systems: when constraints arrive in a stream and the dimension is fixed (e.g. two resource limits), $O(n)$ LP means you can certify feasibility without expensive solvers.
• Randomized LP algorithms: Megiddo's framework motivated Seidel's and Clarkson's randomized $O(n)$ algorithms, which are simpler to implement and widely used in practice for 2D/3D problems.
• Teaching algorithm design: the prune-and-search pattern — pair, pivot, discard, recurse — is a clean paradigm that sits alongside divide-and-conquer and the master theorem in any advanced algorithms course.

Understand Megiddo's algorithm and you hold the key to a wide family of efficient geometry algorithms that underpin graphics engines, GIS tools, and planning software worldwide.

Megiddo's 1984 algorithm carries a clean message: polynomial time is not the end of the story. General LP is polynomial, but by fixing the dimension to 2 or 3 the same problem collapses to linear time — the best possible, since you cannot avoid reading every constraint.

The prune-and-search paradigm behind the result has since become a cornerstone of computational geometry, appearing wherever a divide-and-discard strategy can exploit the low dimension of the problem. It is a reminder that structure in a problem's geometry can be as powerful as any algebraic insight.

If you want to dig deeper, explore how linear programming scales in higher dimensions, or how selection and median finding — the linear-time subroutine at the heart of Megiddo's method — works in its own right.