The medial axis of the union of inner Voronoi balls in the plane

Consider a dense sampling S of the smooth boundary of a planar shape O, i.e., an open subset of R-2. We show that the medial axis of the union of Voronoi balls centered at Voronoi vertices inside O has a particularly simple structure: it is the union of all Voronoi vertices inside O and the Voronoi edges connecting them. Therefore, the medial axis of the union of these inner balls can be computed more efficiently and robustly than for a general union of balls. Our algorithm requires only the computation of a single Delaunay triangulation which is of complexity O(n log n), whereas the general algorithm needs two Delaunay triangulations and a power diagram of quadratic complexity in the number of inner Voronoi balls. Also, our solution yields robust results even without using exact arithmetic, because it avoids the computation of the power diagram of the inner Voronoi balls whose configuration is highly degenerate. (C) 2012 Elsevier B.V. All rights reserved.