  The alpha complex is a fundamental data structure from computational
geometry, which encodes the topological type of a union of balls $B(x; r)
\subset \mathbb{R}^m$ for $x\in S$, including a weighted version that allows
for varying radii. It consists of the collection of "simplices" $\sigma =
\{x_0, ..., x_k \} \subset S$, which correspond to nomempty $(k + 1)$-fold
intersections of cells in a radius-restricted version of the Voronoi diagram.
Existing algorithms for computing the alpha complex require that the points
reside in low dimension because they begin by computing the entire Delaunay
complex, which rapidly becomes intractable, even when the alpha complex is of a
reasonable size. This paper presents a method for computing the alpha complex
without computing the full Delaunay triangulation by applying Lagrangian
duality, specifically an algorithm based on dual quadratic programming that
seeks to rule simplices out rather than ruling them in.
