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
Externally publishedYes

Bibliographical note

Funding Information:
We thank Denise Zickler and Philippe Silar for helpful comments on the manuscript, Catherine Gerlinger for technical assistance, and Donal O’Sullivan for editing the English text. This work was supported by grants from the CNRS (UMR 8621), the University Paris IX. J. M. Davière was supported by a grant of the Ministère de l’Enseignement Supérieur et de la Recherche.


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

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


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

Cite this