Convex Hulls and Half-Space Intersection in 3D

Convex Hulls and Half-Space Intersection in 3D

Part 18 turned points into planes and incidence questions into arrangement questions. In three dimensions, that dictionary becomes tangible: the boundary of a convex hull is a polyhedral surface, and the same surface can be described either by its extreme points or by the half-spaces that contain it. This chapter develops both views, then shows how randomized incremental construction maintains the boundary without repeatedly rebuilding it.

The boundary is a structured object

For a finite set $P\subset\mathbb R^3$, the convex hull is

$$ \operatorname{conv}(P)=\left\{\sum_i \lambda_i p_i:\lambda_i\ge 0,\ \sum_i\lambda_i=1\right\}. $$

When $P$ spans three dimensions, its hull is a convex 3-polytope. A vertex is an extreme input point, an edge is a maximal one-dimensional boundary face, and a facet is a maximal planar polygon on the boundary. If every supporting plane contains exactly three hull vertices, every facet is triangular and the hull is simplicial. Coplanar boundary points instead produce polygonal facets unless an implementation triangulates them as a representation choice.

The boundary is a planar graph drawn on a sphere. For a connected convex polytope,

$$V-E+F=2.$$

This Euler relation is more than a theorem to quote: it is a cheap validation oracle. For a closed triangular boundary, double-counting edge–face incidences gives $3F=2E$, hence $F=2V-4$ and $E=3V-6$. Violating either identity usually signals an unmatched horizon edge, inconsistent orientation, or duplicate face.

How large can a 3D hull become?

With $n$ points in three dimensions, a convex hull has only $O(n)$ vertices, edges, and facets. In general position, $V\le n$ and the triangular formulas above make the linear bound explicit. The bound is tight: points on the moment curve $(t,t^2,t^3)$ are all extreme and form a cyclic polytope with linearly many faces in dimension three.

This is a special mercy of 3D. In dimension $d$, hull complexity can be $\Theta(n^{\lfloor d/2\rfloor})$. Even in 3D, however, an algorithm can do quadratic work if every insertion scans every face. Output size and construction time are different questions.

The predicate beneath every face

The 3D orientation predicate is the signed six-times volume of tetrahedron $abcd$:

$$ \operatorname{orient3d}(a,b,c,d)= \det\begin{pmatrix} b_x-a_x&b_y-a_y&b_z-a_z\\ c_x-a_x&c_y-a_y&c_z-a_z\\ d_x-a_x&d_y-a_y&d_z-a_z \end{pmatrix}. $$

Its sign says which side of the oriented plane $abc$ contains $d$; zero means coplanar. Store every triangular face with a consistent outward orientation. Then a point sees that face precisely when it lies strictly on the exterior side. Which sign is “exterior” depends on the vertex convention, so establish it using an interior witness and test it rather than memorizing a sign.

Randomized incremental hull construction

First remove exact duplicates and find four affinely independent points. Their tetrahedron is an initial hull, oriented so a point known to be inside lies behind every face. Randomly permute the remaining points. When inserting $p$:

1. Find all boundary faces visible from $p$.
2. Find the horizon: edges incident to one visible and one nonvisible face.
3. Delete the visible patch.
4. For every consistently ordered horizon edge $(u,v)$, create triangle $(u,v,p)$ with outward orientation.
5. Repair adjacency and redistribute unresolved conflicts.

The visible facets form a connected patch on a convex polytope, and its boundary is a cycle. That cycle is exactly the horizon. Joining $p$ to it replaces the portion of the old hull exposed to $p$ with a cone of new faces.

A conflict graph avoids scanning the whole boundary. Its bipartite nodes are uninserted points and current facets; edge $(p,f)$ exists when $p$ sees $f$. To insert $p$, follow its incident edges to obtain the visible faces. A new face can conflict only with points that conflicted with a deleted face adjacent to its horizon edge, so candidate redistribution stays local. Remove deleted face nodes and the inserted point node after rebuilding the patch.

def orient3d(a, b, c, d):
    ax, ay, az = (b[i] - a[i] for i in range(3))
    bx, by, bz = (c[i] - a[i] for i in range(3))
    cx, cy, cz = (d[i] - a[i] for i in range(3))
    return (ax * (by*cz - bz*cy)
            - ay * (bx*cz - bz*cx)
            + az * (bx*cy - by*cx))

def insert_point(hull, p, conflicts):
    visible = set(conflicts.faces_seen_by(p))
    if not visible:                 # p is inside or on the boundary
        return

    horizon = []
    candidates = set()
    for face in visible:
        candidates.update(conflicts.points_for(face))
        for edge, neighbor in hull.adjacent_edges(face):
            if neighbor not in visible:
                horizon.append((edge, neighbor))

    hull.remove_faces(visible)
    new_faces = [hull.make_outward_face(edge, p)
                 for edge, _ in order_horizon_cycle(horizon)]
    hull.stitch_cycle(new_faces)

    conflicts.remove_faces(visible)
    conflicts.remove_point(p)
    for q in candidates - {p}:
        for face in new_faces:
            if hull.is_visible(face, q):
                conflicts.add(q, face)

The code deliberately delegates horizon ordering, stitching, and robust visibility. Those are the hard contracts. A half-edge structure makes them explicit: each directed half-edge stores its origin, face, next edge, and twin. A face stores three half-edges and perhaps a conflict list; a vertex stores an incident half-edge. A simpler triangle-plus-edge-map representation can work, but every undirected boundary edge must still have exactly two oppositely directed incidences.

Why random order helps

Backward analysis gives the expected bound. Consider the hull after the first $r$ randomly ordered points. A newly created triangular face is defined by three inserted points and survives only when all earlier points lie behind its plane. Reverse the process: removing the last random point changes only faces incident to that vertex. Because a 3D hull has $O(r)$ edges and faces, the average vertex degree is constant, so the expected number of structural changes caused by insertion $r$ is $O(1)$.

Conflict maintenance adds point–face bookkeeping. Summed over a random permutation, the expected work is $O(n\log n)$ with linear expected structural storage under the standard analysis. This is an expectation over the algorithm’s permutation, not an assumption that the input is random. A malicious geometric order therefore loses its power once the algorithm shuffles independently. See the randomized-algorithms deep dive for indicator variables, backward analysis, and tail-conscious testing.

The half-space view and duality

A bounded convex polytope also has an H-representation,

$$K=\bigcap_i\{x:a_i\cdot x\le b_i\},$$

while a point hull is a V-representation, $K=\operatorname{conv}\{p_i\}$. Converting between them is facet enumeration versus vertex enumeration. If the origin lies strictly inside and inequalities are normalized to $a_i\cdot x\le1$, polarity maps the plane to the point $a_i$: facets of $K$ correspond to vertices of the polar $K^\circ$, vertices correspond to facets, and inclusion reverses. This is the 3D continuation of the point–line order reversal in Part 18.

Unbounded intersections, inequalities with $b_i=0$, and an origin outside the feasible interior need special treatment—translation, homogeneous/projective coordinates, or a direct half-space algorithm. Duality is a mathematical reduction, not permission to divide by a nearly zero offset.

The lifting map from Part 17,

$$ (x,y)\mapsto(x,y,x^2+y^2), $$

connects these ideas directly. The lower facets of the lifted 3D convex hull project to the planar Delaunay triangulation; their supporting planes encode empty circles. The upper envelope/half-space counterpart yields the Voronoi structure described in Part 16. Thus a robust 3D hull engine is also a route to planar proximity structures.

Degeneracy policy and validation

Duplicate points should be canonicalized before construction while retaining source IDs if provenance matters. If all points are collinear or coplanar, report the lower-dimensional hull rather than inventing a thin tetrahedron. When a new point is coplanar with a face, choose and document one policy: preserve maximal polygonal facets, triangulate them consistently, or apply symbolic perturbation. An arbitrary floating epsilon can make two adjacent faces disagree about the same point.

Robust software commonly uses a fast floating filter, an error bound, then adaptive exact expansion arithmetic when the sign is uncertain. Deterministic tie-breaking handles exact zeros after the predicate has proved they are zeros. Do not mix an epsilon decision at one call site with exact signs at another.

After every insertion—or at least in debug builds—check:

• every half-edge has one twin and the directions oppose;
• every triangular face has three distinct vertices and nonzero orientation;
• adjacent faces agree on their shared edge;
• a fixed interior witness lies on the nonvisible side of every face;
• no processed point lies strictly outside any boundary face;
• the boundary is connected and satisfies $V-E+F=2$;
• for a triangulated closed hull, $3F=2E$.

From hulls to proximity and terrain

Three-dimensional hulls close the conceptual loop begun with planar duality: predicates create topology, topology supports local updates, and dual representations expose a second interpretation of the same boundary. Part 20 will turn from exact polyhedral boundaries to terrain and surface algorithms, where triangulated height fields, contours, visibility, and approximation must coexist. The proximity/terrain capstone will then combine Voronoi nearest-site structure, Delaunay triangulation, and the 3D robustness discipline developed here into one end-to-end geometric pipeline.