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

The straight skeleton of a polygon is a variant of the medial axis introduc ed 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 skel eton of an n-gon with r reflex vertices in time O (n(1+epsilon) + n(8/11+ep silon)r(9/11+epsilon)), for any fixed epsilon > 0, improving the previous b est upper bound of O(nr log n). Our algorithm simulates the sequence of col lisions between edges and vertices during the shrinking process, using a te chnique of Eppstein for maintaining extrema of binary functions to reduce t he problem of finding successive interactions to two dynamic range query pr oblems: (1) maintain a changing set of triangles in R-3 and answer queries asking which triangle is first hit by a query ray, and (2) maintain a chang ing set of rays in R-3 and answer queries asking for the lowest intersectio n of any ray with a query triangle. We also exploit a novel characterizatio n of the straight skeleton as a lower envelope of triangles in R-3. The sam e time bounds apply to constructing non-self-intersecting offset curves wit h mitered or beveled corners, and similar methods extend to other problems of simulating collisions and other pairwise interactions among sets of movi ng objects.