Near-linear time medial axis approximation of smooth curves in $\mathbb{R}^3$

Christian Scheffer

Abstract


We present the first algorithm to approximate the medial axis $M_{\gamma}$ of a smooth, closed curve $\gamma \subset \mathbb{R}^3$ in near-linear time. Our algorithm works on a sufficiently dense \eps-sample and comes with a convergence guarantee for the non-discrete, but continuous approximation object. 

As our approach also works correctly for a set of curves, we discuss the following application of the medial axis: The medial axis of two curves $\gamma_1$ and $\gamma_2$ can be applied to compute piecewise-linear simplifications of $\gamma_1$ and $\gamma_2$. In particular, a controllable tradeoff between the degree of simplification and the degree of falsification of the summed Fr\'{e}chet distance between $\gamma_1$ and $\gamma_2$ is obtained.

Finally, we show that for simplifying $\gamma_1$ and $\gamma_2$, our approximation, instead of $M_{\gamma}$, can be applied while guaranteeing the same result.


Full Text:

PDF


DOI: http://dx.doi.org/10.20382/jocg.v7i1a17

ISSN: 1920-180X