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},
  Pages = {145--150},
	Year = {2015}}