## 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 (n^{1+ε} + n^{8/11+ε}r^{9/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