Abstract
The straight skeleton of a polygon is a variant of the medial axis, defined by a shrinking process in which each edge of the polygon moves inward at a fixed rate. The straight skeleton of an n-gon with r reflex vertices in time O(n1+ε+n8/11+ε r9/11+ε) is constructed, for any fixed ε>0. The 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. The characterization of the straight skeleton as a lower envelope of triangles in R3 is discussed.
| Original language | English (US) |
|---|---|
| Pages | 58-67 |
| Number of pages | 10 |
| State | Published - 1998 |
| Externally published | Yes |
| Event | Proceedings of the 1998 14th Annual Symposium on Computational Geometry - Minneapolis, MN, USA Duration: Jun 7 1998 → Jun 10 1998 |
Other
| Other | Proceedings of the 1998 14th Annual Symposium on Computational Geometry |
|---|---|
| City | Minneapolis, MN, USA |
| Period | 6/7/98 → 6/10/98 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics