## Abstract

We present a new algorithm to compute a motorcycle graph. It runs in O(n√nlogn) time when n is the size of the input. We give a new characterization of the straight skeleton of a polygon possibly with holes. For a simple polygon, we show that it yields a randomized algorithm that reduces the straight skeleton computation to a motorcycle graph computation in O(nlog^{2}n) time. Combining these results, we can compute the straight skeleton of a non-degenerate simple polygon with n vertices, among which r are reflex vertices, in O(nlog^{2}n + r√logr) expected time. For a degenerate simple polygon, our expected time bound becomes O(nlog^{2}n + r17/u+ϵ).

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

Title of host publication | Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 |

Publisher | Association for Computing Machinery |

Pages | 156-165 |

Number of pages | 10 |

Volume | 06-08-January-2002 |

ISBN (Electronic) | 089871513X |

State | Published - 2002 |

Externally published | Yes |

Event | 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States Duration: Jan 6 2002 → Jan 8 2002 |

### Other

Other | 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 |
---|---|

Country/Territory | United States |

City | San Francisco |

Period | 01/6/02 → 01/8/02 |

## ASJC Scopus subject areas

- Software
- Mathematics(all)