language: en

Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions

David Eppstein Jeff Erickson

[Submitted to Discrete & Computational Geometry]

July 1, 1998

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+" + n 8=11+" r 9=11+" ), for any fixed " &gt; 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 IR 3 and answer queries asking which triangle would be first hit by a query ray, and (2) maintain a changing set of rays in IR 3 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 IR 3 . 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.

[An extended abstract of this paper was presented at the 14th Annual ACM Symposium on Computational Geometry [29]. See http:/// ~ jeffe/pubs/cycles:html for the most recent version of this paper.]

Department of Information and Computer Science, University of California,
Irvine, CA 92697, USA;
epp-stein@ics.uci.edu;

[Research partially supported by NSF grant CCR-9258355 and by matching funds from Xerox Corporation.]

Center for Geometric Computing, Department of Computer Science, Duke University,
Box 90129, Durham, NC 27708-0129, USA;
jeffe@cs.duke.edu;

[Research supported by NSF grant DMS-9627683 and by U. S. Army Research Office MURI grant DAAH04-96-1-0013.]