Computing the Straight Skeleton of a Monotone Polygon in O(nlogn) Time
Gautam K. Das, Asish Kumar Mukhopadhyay, Subhas Chandra Nandy, Sangameswar Patil, S. Venugopal Rao · Canadian Conference on Computational Geometry · 2010
The straight skeleton of a simple polygon is defined as the trace of the vertices when the initial polygon is shrunken in self-parallel manner [2]. In this paper, we propose a simple algorithm for drawing the straight skeleton of a monotone polygon. The time and space complexities of our algorithm are O(nlogn) and O(n) respectively.