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

Original language | English (US) |
---|---|

Pages | 58-67 |

Number of pages | 10 |

State | Published - Jan 1 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