Eppstein, D.; Erickson, J. Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions. (English) Zbl 0946.68147 Discrete Comput. Geom. 22, No. 4, 569-592 (1999). Summary: The straight skeleton of a polygon is a variant of the medial axis introduced by O. Aichholzer, F. Aurenhammer, D. Alberts and B. Gärtner [A novel type of skeleton for polygons. H. Maurer (ed.) et al., J.UCS. The Journal of Universal Computer Science. Vol. 1, 1995. Annual print and CD-ROM archive edition. With 1 CD-ROM. Berlin: Springer-Verlag. 752-761 (1996)], 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+ \varepsilon}+ n^{8/11+ \varepsilon} r^{9/11+ \varepsilon})\), for any fixed \(\varepsilon> 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 dynamics range query problems: (1) maintain a changing set of triangles in \(\mathbb{R}^3\) and answer queries asking which triangle is first hit by a query ray, and (2) maintain a changing set of rays in \(\mathbb{R}^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 \(\mathbb{R}^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. Cited in 25 Documents MSC: 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) Keywords:straight skeleton of a polygon PDFBibTeX XMLCite \textit{D. Eppstein} and \textit{J. Erickson}, Discrete Comput. Geom. 22, No. 4, 569--592 (1999; Zbl 0946.68147) Full Text: DOI