Raising roofs, crashing cycles, and playing pool:
Applications of a data structure for finding pairwise interactions

Proceedings of the 14th Annual ACM Symposium on Computational Geometry, 58-67, 1998.

• Journal version (final except for copy-editing, © 1999 Springer-Verlag):
• Offical journal version from Springer-Verlag (subscription required)

• SoCG version (© 1998 ACM):
• Official SoCG version from the ACM Digital Library (subscription or $5 payment required)

• Related work

Abstract:

The straight skeleton of a polygon is a variant of the medial axis introduced by Aichholzer et al., defined by a shrinking process in which each edge of the polygon moves inward at a fixed rate. We construct the straight skeleton of an n-gon with r reflex vertices in time O(n^1+e + n^8/11+er^9/11+e) = O(n^17/11+e), for any fixed e>0, improving the previous best upper bound of O(nr log n). Our algorithm simulates the sequence of collisions between edges and vertices during the shrinking process, using a technique of Eppstein for maintaining extrema of binary functions to reduce the problem of finding successive interactions to two dynamic range query problems: (1) maintain a changing set of triangles in R³ and answer queries asking which triangle is first hit by a query ray, and (2) maintain a changing set of rays in R³ and answer queries asking for the lowest intersection of any ray with a query triangle. We also exploit a novel characterization of the straight skeleton as a lower envelope of triangles in R³. The same time bounds apply to constructing non-self-intersecting offset curves with mitered or beveled corners, and similar methods extend to other problems of simulating collisions and other pairwise interactions among sets of moving objects.

Related work

• Some easy special cases of motorcycle graphs

• David's related research on maintaining closest pairs

• Florence Cloppet, Jean-Michel Oliva, and George Stamon, "Angular bisector network, a simplified generalized Voronoi diagram: Application to processing complex intersections in biomedical images", IEEE PAMI 22(1):120-128, 2000.

• Petr Felkel and Jirí Zara, "The Roof Construction Problem", Proc. CTU Workshop '93 Vol. I: Informatics & Cybernetics, 85-86, 1993. Possibly the earliest correct desription of the straight skeleton?

• Petr Felkel and Stepán Obdrzálek, "Straight skeleton implementation", Proc. 14th Spring Conf. Computer Graphics, 210-218, 1998. This paper describes a straight skeleton algorithm with running time O(n log n + nr), different from the one described in our paper and possibly discovered earlier. C++ source code is available from the authors.

• Jean-Michel Oliva, M. Perrin, Sabine Coquillart, "3d reconstruction of complex polyhedral shapes from contours using a simplified generalized Voronoï diagram", Computer Graphics Forum 15(3):C397-C408, 1996 (Proc. Eurographics '96). Defines the straight skeleton, here called the "angular bisector network", and uses it to reconstruct polyhedra from parallel slices.

Publications - Jeff Erickson (jeffe@cs.duke.edu) 14 Feb 2002