Engineering an efficient algorithm for finding the straight skeleton of a simple polygonAmit Parnerkar, Sarnath Ramnath, YenChang 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 starshaped polygons. Our experimental results show that for starshaped 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 foldandcut 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 nearlylinear 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 (nonconvex) 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 starshaped 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, SpringerVerlag London, 1996 3. P. Felkel and S. Obdrzálek, Straight Skeleton Implementation. 14th Spring Conference on Computer Graphics, Slovakia,1998, pages 210218 4. Franz Aurenhammer et al., Straight skeleton of a simple polygon, Symposium of LIESMARS, China, 1995, pages 114124 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. SiuWing Cheng, Antoine Vigneron, Motorcycle graphs and straight skeletons, ACMSIAM 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 619628 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://wwwusers.cs.umn.edu/~janardan/rppresoverview_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 FoldandCut 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): 405420 (1999). 

Straight Skeleton for Starshaped polygon of 100 vertices 

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