### 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(n + k) log n)-time algorithm for solving this problem and sketch a faster O((n + k) 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) |
---|---|

Pages (from-to) | 109-140 |

Number of pages | 32 |

Journal | Algorithmica |

Volume | 4 |

Issue number | 1 |

DOIs | |

State | Published - Dec 1989 |

### Keywords

- Computational geometry
- Geodesic metric
- Shortest paths
- Simple polygons
- Voronoi diagrams

### ASJC Scopus subject areas

- Computer Science(all)
- Computer Science Applications
- Applied 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. (1989). On the geodesic voronoi diagram of point sites in a simple polygon.

*Algorithmica*,*4*(1), 109-140. https://doi.org/10.1007/BF01553882