Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions

David Eppstein, Jeff Erickson

Research output: Contribution to conferencePaperpeer-review

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 languageEnglish (US)
Pages58-67
Number of pages10
StatePublished - Jan 1 1998
Externally publishedYes
EventProceedings of the 1998 14th Annual Symposium on Computational Geometry - Minneapolis, MN, USA
Duration: Jun 7 1998Jun 10 1998

Other

OtherProceedings of the 1998 14th Annual Symposium on Computational Geometry
CityMinneapolis, MN, USA
Period6/7/986/10/98

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions'. Together they form a unique fingerprint.

Cite this