×

Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions. (English) Zbl 0946.68147

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.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI