Subquadratic medial-axis approximation in $\mathbb{R}^3$

Abstract

We present an algorithm that approximates the medial axis of a smooth manifold in $\mathbb{R}^3$ which is given by a sufficiently dense point sample. The resulting, non-discrete approximation is shown to converge to the medial axis as the sampling density approaches infinity. While all previous algorithms guaranteeing convergence have a running time quadratic in the size $n$ of the point sample, we achieve a running time of at most $\mathcal{O}(n\log^3 n)$. While there is no subquadratic upper bound on the output complexity of previous algorithms for non-discrete medial axis approximation, the output of our algorithm is guaranteed to be of linear size.