O. Aichholzer, W. Aigner, F. Aurenhammer, T. Hackl, B. Jüttler, and
M. Rabl
We present a simple, efficient, and stable method for computing--with any
desired precision--the medial axis of simply connected planar domains. The
domain boundaries are assumed to be given as polynomial spline curves. Our
approach combines known results from the field of geometric approximation
theory with a new algorithm from the field of computational geometry.
Challenging steps are (1) the approximation of the boundary spline such that
the medial axis is geometrically stable, and (2) the efficient decomposition
of the domain into base cases where the medial axis can be computed directly
and exactly. We solve these problems via spiral biarc approximation and a
randomized divide & conquer algorithm.