Skeletonization of a~multiply-connected polygonal domain based on its boundary adjacent tree

L. M. Mestetskiy

Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 9 (2006) no. 3, pp. 299-314

Résumé

The problem of a continuous skeleton construction for a multiply connected polygonal domain is considered. The polygonal domain is a closed one, whose boundary consists of a finite number of simple polygons. The $O(n\log n)$ – algorithm for the worse case is offered, where $n$ is the number of polygonal domain vertices. The proposed algorithm creates the dual graph for the Voronoi diagram of the domain boundary. The solution is based on the adjacent tree of all the boundary polygons created by a sweepline method. In this case, sites and polygons are called adjacent if they have a common contact empty circle. The offered approach generalizes the Lee skeleton algorithm from a simple polygon to that with holes with the same running time.