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

Written with David Eppstein.
Discrete & Computational Geometry 22(4):569-592, 1999.
(Special issue of invited papers from the 14th Annual ACM Symposium on Computational Geometry)

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

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(n1+e + n8/11+er9/11+e) = O(n17/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 R3 and answer queries asking which triangle is first hit by a query ray, and (2) maintain a changing set of rays in R3 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 R3. 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

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