Seidel's LP Algorithm

Purpose: Solve a linear program with $n$ constraints in fixed dimension $d$ in expected $O(d!n)$ — linear in $n$, which is exactly what low-dimensional geometry problems need.

The Idea: randomized incremental with backwards analysis

1. Shuffle the constraints randomly.
2. Add them one at a time, maintaining the current optimum $x^{\ast }$.
3. When constraint $i$ is added:
   • if $x^{\ast }$ already satisfies it, nothing changes — this is the common case;
   • otherwise the new optimum must lie on the boundary hyperplane of constraint $i$. Project the previous $i-1$ constraints onto that hyperplane and solve a $(d-1)$-dimensional LP recursively.

The analysis (backwards analysis)

After $i$ constraints have been added, the optimum is determined by exactly $d$ of them. Since the order was random, the probability that the $i$-th constraint added is one of those $d$ is $d/i$. So the expected cost is

$T_d(n)=O(n)+{\sum }_{i=1}^n\frac{d}{i}{T}_{d-1}(i)=O(d!n).$

The $d!$ is harmless for $d=2$ or $3$ — which covers essentially every geometric LP that appears in practice.

Complexity

• Time: $O(d!n)$ expected
• Space: $O(n)$
• Deterministic alternative: Megiddo’s algorithm, $O(2^{2^d}n)$ — linear in $n$ but with a far worse constant

Backwards analysis is the real lesson

“What is the probability that the last element added was important?” is a remarkably powerful proof technique. It gives clean expected bounds for:

Algorithm	Backwards analysis says
Seidel’s LP	\Pr[\text{i-th constraint is binding}] = d/i
Welzl’s minimum enclosing circle	\Pr[\text{i-th point is on the circle}] = 3/i
Randomized incremental Delaunay	expected $O(1)$ structural change per insertion
Randomized quicksort	expected $O(n\log n)$
Treap depth	expected $O(\log n)$

Learning to run this argument is worth more than memorising any single algorithm on the list.

Contest applications of 2D/3D LP

• Half-plane intersection feasibility — is the intersection of $n$ half-planes non-empty? That is a 2D LP.
• Chebyshev centre — the largest inscribed circle in a convex polygon
• Smallest enclosing circle — an LP-type problem; Welzl is the specialised version
• Line fitting under $L_{\infty }$ — minimise the maximum vertical error, a 2D LP
• Feasibility of difference constraints — although those are better solved by Bellman-Ford

LP-type problems

Seidel’s algorithm generalises to any LP-type problem: an optimisation over a set system with a well-defined “combinatorial dimension” $d$, satisfying monotonicity and locality axioms. Minimum enclosing ball, minimum enclosing ellipsoid, smallest enclosing annulus, and distance between polytopes are all LP-type, and all solvable in expected $O(n)$ for fixed dimension by the same framework (Sharir-Welzl, Matoušek-Sharir-Welzl).

Variants / Use Cases

• Welzl’s algorithm — the minimum enclosing circle special case
• Half-Plane Intersection — the $O(n\log n)$ construction when you need the whole region, not just a point
• Simplex method — the general-purpose LP algorithm for large $d$; exponential worst case, excellent in practice
• Geometry — the branch overview