Motorcycle graphs and straight skeletons

ABSTRACT

We present a new algorithm to compute a motorcycle graph. It runs in O(n√n log n) time when n is the size of the input. We give a new characterization of the straight skeleton of a polygon possibly with holes. For a simple polygon, we show that it yields a randomized algorithm that reduces the straight skeleton computation to a motorcycle graph computation in O(n log² n) time. Combining these results, we can compute the straight skeleton of a non-degenerate simple polygon with n vertices, among which r are reflex vertices, in O(n log²n + r√r log r) expected time. For a degenerate simple polygon, our expected time bound becomes O(n log² n + r^17/11+ε).

REFERENCES

• 1: Pankaj K. Agarwal, Partitioning arrangements of lines, part I: an efficient deterministic algorithm, Discrete & Computational Geometry, v.5 n.5, p.449-483, 1990 [doi>10.1007/BF02187805]
• 2: Oswin Aichholzer , Franz Aurenhammer, Straight Skeletons for General Polygonal Figures in the Plane, Proceedings of the Second Annual International Conference on Computing and Combinatorics, p.117-126, June 17-19, 1996
• 3: O. Aichholzer, F. Aurenhammer, D. Alberts, and B. Gärtner. A novel type of skeleton for polygons. The Journal of Universal Computer Science, 1(1995), 752-761.
• 4: H. Blum. A transformation for extracting new descriptors of shape. In Models for the Perception of Speech and Visual Form, (eds. W. Wathen-Dunn), 362-380, 1967, M.I.T. Press.
• 5: Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993 [doi>10.1007/BF02189314]
• 6: B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry. Combinatorica, 10 (1990), 229-249.
• 7: B. Chazelle , L. J. Guibas, Visibility and intersection problems in plane geometry, Discrete & Computational Geometry, v.4 n.6, p.551-581, Sep. 1989 [doi>10.1007/BF02187747]
• 8: F. Chin, J. Snoeyink, and C. A. Wang. Finding the medial axis of a simple polygon in linear time. Discrete Comput. Geom., 21 (1999), 405-420.
• 9: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 10: Erik D. Demaine , Martin L. Demaine , Joseph S. B. Mitchell, Folding flat silhouettes and wrapping polyhedral packages: new results in computational origami, Proceedings of the fifteenth annual symposium on Computational geometry, p.105-114, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304933]
• 11: Erik D. Demaine , Martin L. Demaine , Anna Lubiw, Folding and Cutting Paper, Revised Papers from the Japanese Conference on Discrete and Computational Geometry, p.104-118, December 09-12, 1998
• 12: Erik D. Demaine , Martin L. Demaine , Anna Lubiw, Folding and one straight cut suffice, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.891-892, January 17-19, 1999, Baltimore, Maryland, United States
• 13: D. Eppstein and J. Erickson. Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions. Discrete Comput. Geom., 22 (1999), 569-592.
• 14: Sariel Har-Peled, Constructing Planar Cuttings in Theory and Practice, SIAM Journal on Computing, v.29 n.6, p.2016-2039, April 2000 [doi>10.1137/S0097539799350232]
• 15: J. Hershberger, Finding the upper envelope of n line segments in O(n log n) time, Information Processing Letters, v.33 n.4, p.169-174, December 1989 [doi>10.1016/0020-0190(89)90136-1]
• 16: John Hershberger , Subhash Suri, A pedestrian approach to ray shooting: shoot a ray, take a walk, Journal of Algorithms, v.18 n.3, p.403-431, May 1995
• 17: J. Matoušek. On constants for cuttings in the plane. Discrete Comput. Geom., 20 (1998), 427-448.
• 18: Jiří Matoušek, Construction of &egr;-nets, Discrete & Computational Geometry, v.5 n.5, p.427-448, 1990 [doi>10.1007/BF02187804]
• 19: Jiří Matoušek, Cutting hyperplane arrangements, Discrete & Computational Geometry, v.6 n.5, p.385-406, 1991 [doi>10.1007/BF02574697]
• 20: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983