A straightforward algorithm for computing the medial axis of a simple polygon

摘要

A new algorithm for computing the medial axis of a simple polygon is presented. Although the algorithm runs inO(kN) time wherekis the hierarchy of the Voronoi diagram of the polygon ranging fromO(N) toO(logN) it is simple to implement and it does not require the complex data-structures required for the faster methods. This is an important factor in many applications of the medial axis.