Motorcycle graphs and straight skeletons

Siu Wing Cheng*, Antoine Vigneron

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

41 Scopus citations


We present a new algorithm to compute motorcycle graphs. It runs in O(n √n log n) time when n is the number of motorcycles. We give a new characterization of the straight skeleton of a nondegenerate polygon. For a polygon with n vertices and h holes, we show that it yields a randomized algorithm that reduces the straight skeleton computation to a motorcycle graph computation in expected O(n√h+1 log 2 n) time. Combining these results, we can compute the straight skeleton of a nondegenerate polygon with h holes and with n vertices, among which r are reflex vertices, in O(n√h+1 log 2 n + r √r log r)expected time. In particular, we cancompute the straight skeleton of a nondegenerate polygon with n vertices in O(n√nlog 2 n expected time.

Original languageEnglish (US)
Pages (from-to)159-182
Number of pages24
JournalAlgorithmica (New York)
Issue number2
StatePublished - Feb 2007


  • Computational geometry
  • Medical axis
  • Motorcycle graph
  • Randomized algorithm
  • Straight skeleton

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Motorcycle graphs and straight skeletons'. Together they form a unique fingerprint.

Cite this