Half-Plane Intersection and Low-Dimensional Linear Programming

Half-Plane Intersection and Low-Dimensional Linear Programming

Part 9 simplified a polygon by adding diagonals. This part takes the opposite view: instead of subdividing a region we describe it implicitly, as all points satisfying a collection of inequalities. The result may still be a polygon, but now every edge is a certificate that one constraint has become tight. That shift—from boundary construction to feasible-set reasoning—is the gateway from computational geometry to optimization.

Consider a casting that must slide out of a mold in direction (v). Every mold face rules out directions that would drive the casting into that face. In a two-dimensional cross-section, each rule keeps one side of a line. A direction works only if it survives every rule. This is the central picture:

\[ H_i=\{x\in\mathbb R^2:a_i x_1+b_i x_2\le c_i\},\qquad F=\bigcap_{i=1}^n H_i. \]

Each (H_i) is a closed half-plane, and (F) is the feasible region. Because an intersection of convex sets is convex, (F) is convex even before we compute it. It may be a bounded polygon, an unbounded wedge or strip, a segment, a point, or empty.

Reading a System of Inequalities Geometrically

The sign of (a_ix+b_iy-c_i) classifies a point relative to constraint (i). The vector ((a_i,b_i)) is the boundary line's outward normal: walking in that direction increases the left side and eventually violates the inequality. Adding constraints can only shrink (F). This monotonicity makes incremental algorithms possible.

The diagram suggests a useful certificate table:

The final claim is Helly's theorem specialized to the plane: if a finite family of convex sets has empty intersection, some three already have empty intersection. It explains why low-dimensional LP can repair violations using tiny subproblems.

Constructing the Whole Intersection

If we need the boundary of $F$, not merely one optimum, a standard $O(n\log n)$ algorithm sorts boundary lines by direction and scans them with a deque. Orient each line so its allowed half-plane lies to its left. Lines with the same direction are consolidated: retain the most restrictive one; opposite parallel lines can form a strip or prove infeasibility.

For each new line, inspect the intersection of the last two deque lines. While that corner lies outside the new half-plane, remove the back line. Apply the same test at the front. Then append the new line. After all lines arrive, repeat the cleanup between the two ends and intersect consecutive surviving lines.

Why can lines be discarded permanently? With directions in circular order, the feasible polygon's supporting edges occur in that same order. If the new constraint cuts away the corner made by two adjacent candidates, the middle line cannot reappear later on the convex boundary. The deque is therefore the constraint-space analogue of the stack used for a convex hull.

An implementation should not literally sort by atan2. Classify directions by half-plane and compare them with exact cross products. Compute line intersections only when needed, and classify a corner against a half-plane with determinant signs where possible. If the input uses exact integer coefficients, filtered predicates—fast floating point followed by exact arithmetic near zero—often provide the best balance.

Incremental Linear Programming in Two Dimensions

When the desired output is only an optimum, constructing every vertex can be unnecessary. Start with an enclosing box large enough for the application's known domain and process constraints one by one. Keep the optimum for the constraints seen so far. If a new constraint contains that point, nothing changes. Otherwise the new optimum, if one exists, must lie on the new boundary line: the old optimum has just been cut off, so sliding the objective back toward feasibility first meets that line.

Restrict every earlier half-plane to the new line. Parameterize the line as $p(t)=p_0+tu$. Each constraint becomes a one-dimensional lower bound, upper bound, no restriction, or contradiction on $t$. Intersect those intervals, then choose the feasible endpoint preferred by the objective. Scanning all earlier constraints after every violation gives a simple deterministic $O(n^2)$ algorithm in the worst case—excellent as a reference implementation and often adequate for modest inputs.

def incremental_lp(constraints, objective, bounding_box):
    """Minimize objective·x; geometric primitives use robust predicates."""
    active = list(bounding_box)       # makes the initial problem bounded
    optimum = solve_constant_size(active, objective)

    for halfplane in constraints:
        if contains(halfplane, optimum):
            active.append(halfplane)
            continue

        # A replacement optimum must lie on halfplane.boundary.
        interval = whole_parameter_line()
        for previous in active:
            interval = interval.intersect(
                restrict_to_line(previous, halfplane.boundary)
            )
            if interval.is_empty():
                return None          # infeasible certificate is available

        optimum = preferred_endpoint(interval, halfplane.boundary, objective)
        active.append(halfplane)

    return optimum

The box is a modeling choice, not a numerical trick. If the original problem may be unbounded, solve without a box or mark which optimum touches an artificial side; then distinguish a genuine finite answer from an improving ray. Likewise, None should mean mathematically infeasible, not “a division produced NaN.”

Random Order and Seidel's Insight

Seidel's low-dimensional LP algorithm randomizes the constraint order. When a new constraint is violated, it becomes part of the solution's basis and the algorithm recursively solves a problem one dimension lower on that constraint's boundary. In 2D the repair is a 1D interval problem; in 1D a repair reaches a point. At most (d) constraints define a basis in dimension (d).

The intuition behind expected linear time for fixed (d) is backward analysis. Among the first (i) randomly ordered constraints, only basis constraints—at most (d)—could have been inserted last and forced a repair. Thus the probability of repair at step (i) is at most (d/i). Repairs become rarer as the prefix grows, and their expected total work satisfies a linear recurrence when (d) is constant. Randomness improves the expected running time; it does not soften the constraints or approximate the answer.

For dimension $d$ treated as a constant, randomized LP takes expected $O(d!n)$-type time with small linear dependence on $n$; constants grow rapidly with dimension. When dimension is part of the input, ordinary linear programming machinery is appropriate. “Linear time” here means linear in the number of constraints for fixed dimension, not a universal bound independent of $d$.

A Nonlinear-Looking Example: Smallest Enclosing Disc

Given points (p_i), the smallest enclosing disc minimizes radius (r) subject to (|c-p_i|\le r). These constraints are not half-planes in the center coordinates, yet the problem has the same tiny-basis behavior: the optimal disc is determined by at most three points—two endpoints of a diameter, or three points on its circumcircle. Randomized incremental construction therefore mirrors Seidel's algorithm. A point inside the current disc changes nothing; a point outside must lie on the replacement disc's boundary, reducing the repair to a smaller constrained problem. This is an example of an LP-type problem: the combinatorial basis logic survives even though the feasible sets are not linear inequalities.

Contracts, Degeneracies, and What Comes Next

Choose and document a boundary convention: this chapter uses closed half-planes, so points on a line are feasible. Normalize neither line equations nor normals unless the arithmetic model needs it; scaling an inequality by a positive number preserves it, while negative scaling reverses its sense. Handle zero normals as either tautologies or contradictions. Treat same-angle lines before deque processing, detect parallel intersections before division, and preserve lower-dimensional answers rather than declaring every zero-area region empty. For floating inputs, a single global epsilon is not a proof; scale-aware filters and exact fallbacks keep sorting and containment decisions consistent.

Half-plane intersection turns constraints into one convex cell, while Part 11 asks how many sites partition the entire plane into competing cells. The same supporting lines, convexity, unbounded rays, and careful predicates reappear in Voronoi diagrams and Delaunay triangulations—but now the inequalities are generated systematically by distances between sites.