Engineering an efficient algorithm for finding the straight skeleton of a simple polygon

Amit Parnerkar, Sarnath Ramnath, Yen-Chang Wang

Introduction:

We present an algorithm for finding the Straight Line Skeleton of simple polygons that uses a “corrective greedy” approach. The paper examines the behavior of a simple algorithm that attempts to find the straight skeleton using local information only. Since it is well known that local information alone is insufficient to find the straight skeleton [1, 9], the algorithm is at times forced to rollback/backtrack some of the computation done. Since it is hard to get an exact theoretical bound on the number of backtrack operations, we have tested the algorithm extensively on randomly generated star-shaped polygons. Our experimental results show that for star-shaped polygons, this approach gives us an O(n log n) behavior. Implementation for this algorithm is available through an applet at http://web.stcloudstate.edu/rsarnath/skeleton/straightSkeleton.htm

Straight skeleton have several applications, they are; layered manufacturing [10], Drawing Free Trees Inside Rectilinear polygons [11], origami polygon cutting theorem (solve the fold-and-cut problem) [12, 13], Label placement algorithms that locate a label at a centroid [14], to construct a polygonal roof over a set of ground walls [7], reconstruct a geographical terrain from a river map, etc.

Straight skeleton is a concept that was first introduced by Aichholzer in 1995 [1] and is similar to medial axis. Finding medial axis can be achieved in linear time [15], but there are no known linear or nearly-linear algorithms for finding the straight skeleton.

Several researchers have proposed algorithms for this problem. The fastest deterministic algorithm is the one by Eppstein and Erickson [5] which runs in O(n^1+e + n^8/11+e r^9/11+e) where n is the total number of vertices, r is the number of reflex (non-convex) vertices, and e is an arbitrarily small positive constant. More recently, a slightly faster randomized algorithm using O(n Squareroot(n) log n) time and O(n) space was proposed by Cheng and Vigneron [6]. The following table summarizes these results [9].

Result obtained & Analysis:

As mentioned earlier, n denotes the number of vertices and m denotes number of backtracks. Since each backtrack can be computed in log n time using simple data structures, the algorithm runs in O((n + m) log n) time. Since it is hard to get a good theoretical bound on m, we have done this experimentally. To do this, we have focused on the special case of star-shaped polygons (polygons where the entire interior is visible from a single point)

We experimented with randomly generated star shape polygons and plotted the running time with respect to vertex size (n) as shown in figure 4.a For each value of n, we generated 50 instances and took the average of all these running times.

To estimate m, we generated 2000 random polygons of 100 vertices each. For each value of a (backtrack per vertex) we counted the number of input instances that had an (m/n) <= a (cumulative distribution function). This plot for n = 100 and n = 200 is given in figure 4.b

Figure 4: (a) Running time

(b) Cumulative distribution function

The experimental result in figure 4.b suggests that the value of m or the number of extra intersections calculated is not very high. This is further strengthened by the cumulative distribution function whose sigmoid suggests that we can expect a good average case performance from this approach.

References:

1. O. Aichholzer, F. Aurenhammer, D. Alberts, and B. Gartner. A Novel Type of Skeleton for Polygons, J. Universal Comput. Sci., 1995.

2. Oswin Aichholzer, Franz Aurenhammer, Straight Skeletons for General Polygonal Figures in the Plane. Proc. of the Second Annual International Conference on Computing and Combinatorics, Springer-Verlag London, 1996

3. P. Felkel and S. Obdrzálek, Straight Skeleton Implementation. 14th Spring Conference on Computer Graphics, Slovakia,1998, pages 210-218

4. Franz Aurenhammer et al., Straight skeleton of a simple polygon, Symposium of LIESMARS, China, 1995, pages 114-124

5. David Eppstein and Jeff Erickson, Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions, Proc. Of the ACM Symposium on Computational Geometry, 1998, pages 58 - 67

6. Siu-Wing Cheng, Antoine Vigneron, Motorcycle graphs and straight skeletons, ACM-SIAM Symposium on Discrete Algorithms, 2002, pages 156 - 165

7. David Bélanger, Designing Roofs of Buildings, http://www.sable.mcgill.ca/~dbelan2/roofs/roofs.html

8. David Eppstein, Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs, ACM and SIAM, 1998, pages 619-628

9. Jeff Erickson, Straight skeleton of a simple polygon, http://compgeom.cs.uiuc.edu/~jeffe/open/skeleton.html

10. Ravi Janardan, Geometric Algorithms for Rapid Physical Prototyping, http://www-users.cs.umn.edu/~janardan/rpp-res-overview_files/frame.htm

11. A.Bagheri, M.Razzazi, Drawing Free Trees Inside Rectilinear polygons Using Polygon Skeleton, 18th European Workshop on Computational Geometry, 2002

12. Eric Biunno, The Origami Polygon Cutting Theorem, http://transform.tv/EricBiunno/welcome.html

13. Erik Demaine, The Fold-and-Cut Problem, http://theory.lcs.mit.edu/~edemaine/foldcut/#skeleton

14. Hoseok Kang et al. Using Shape Analyses for Placement of Polygon Labels, http://gis.esri.com/library/userconf/proc01/professional/papers/pap388/p388.htm

15. Francis Chin et al. Finding the Medial Axis of a Simple Polygon in Linear Time, Discrete & Computational Geometry 21(3): 405-420 (1999).

Straight Skeleton for Star-shaped polygon of 100 vertices

Straight Skeleton for letter "SCSU" (St Cloud State University)