Delaunay triangulations approximate anchor hulls

摘要

Recent results establish that a subset of the Voronoi diagram of a point set that is sampled from the smooth boundary of a shape approximates the medial axis. The corresponding question for the dual Delaunay triangulation is not addressed in the literature, We show that, for two-dimensional shapes, the Delaunay triangulation approximates a specific structure which we call anchor hulls. As an application we demonstrate that our approximation result is useful for the problem of shape matching. (c) 2006 Elsevier B.V. All rights reserved.