## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 159-182 |

Number of pages | 24 |

Journal | Algorithmica (New York) |

Volume | 47 |

Issue number | 2 |

DOIs | |

State | Published - Feb 2007 |

Externally published | Yes |

## Keywords

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

## ASJC Scopus subject areas

- General Computer Science
- Computer Science Applications
- Applied Mathematics