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 (n1+ε + n8/11+εr9/11+ε), for any fixed ε > 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 ℝ3 and answer queries asking which triangle is first hit by a query ray, and (2) maintain a changing set of rays in ℝ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 ℝ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.
Original language | English (US) |
---|---|
Pages (from-to) | 569-592 |
Number of pages | 24 |
Journal | Discrete and Computational Geometry |
Volume | 22 |
Issue number | 4 |
DOIs | |
State | Published - Dec 1999 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics