### Abstract

Given a simple polygon with n sides in the plane and a set of k point "sites" in its interior or on the boundary, compute the Voronoi diagram of the set of sites using the internal "geodesic" distance inside the polygon as the metric. We describe an O ((n+k )log^{2}(n+k)) time algorithm for solving this problem and sketch a faster 0((n+t)log(n+k)) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question.

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

Title of host publication | Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987 |

Editors | D. Soule |

Publisher | Association for Computing Machinery, Inc |

Pages | 39-49 |

Number of pages | 11 |

ISBN (Electronic) | 0897912314, 9780897912310 |

DOIs | |

State | Published - Oct 1 1987 |

Event | 3rd Annual Symposium on Computational Geometry, SCG 1987 - Waterloo, Canada Duration: Jun 8 1987 → Jun 10 1987 |

### Publication series

Name | Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987 |
---|

### Other

Other | 3rd Annual Symposium on Computational Geometry, SCG 1987 |
---|---|

Country | Canada |

City | Waterloo |

Period | 6/8/87 → 6/10/87 |

### ASJC Scopus subject areas

- Geometry and Topology
- Computational Mathematics

## Fingerprint Dive into the research topics of 'On the geodesic Voronoi diagram of point sites in a simple polygon'. Together they form a unique fingerprint.

## Cite this

Aronov, B. (1987). On the geodesic Voronoi diagram of point sites in a simple polygon. In D. Soule (Ed.),

*Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987*(pp. 39-49). (Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987). Association for Computing Machinery, Inc. https://doi.org/10.1145/41958.41963