An Output-Sensitive Algorithm for Computing Weighted $\alpha$-Complexes

CCCG: The Canadian Conference in Computational Geometry
2015

An $\alpha$-complex is a subcomplex of the Delaunay triangulation of a point set $P\subset \mathbb{R}^d$ that is topologically equivalent to the union of balls of radius $\alpha$ centered at the points of $P$.
In this paper, we give an output-sensitive algorithm to compute $\alpha$-complexes of $n$-point sets in constant dimensions, whose running time is $O(f\log n\log \frac{\alpha}{s})$, where $s$ is the smallest pairwise distance and $f$ is the number of simplices in the $c\alpha$-complex for a constant $c$.
The algorithm is based on a refinement of a recent algorithm for computing the full Delaunay triangulation of $P$.
We also extend the algorithm to work with weighted points provided the weights are appropriately bounded.
The new analysis, which may be of independent interest, bounds the number of intersections of $k$-faces of a Voronoi diagram with $(d-k)$-faces of the Voronoi diagram of a carefully constructed superset.

@inproceedings{sheehy15output, Author = {Donald R. Sheehy}, Booktitle = {Proceedings of the Canadian Conference on Computational Geometry}, Title = {An Output-Sensitive Algorithm for Computing Weighted $\alpha$-Complexes}, Year = {2015}}