## Abstract

Voronoi diagrams of curved objects can show certain phenomena that are often considered artifacts: The Voronoi diagram is not connected; there are pairs of objects whose bisector is a closed curve or even a two-dimensional object; there are Voronoi edges between different parts of the same site (so-called self-Voronoi-edges); these self-Voronoi-edges may end at seemingly arbitrary points not on a site, and, in the case of a circular site, even degenerate to a single isolated point. We give a systematic study of these phenomena, characterizing their differential-geometric and topological properties. We show how a given set of curves can be refined such that the resulting curves define a "well-behaved" Voronoi diagram. We also give a randomized incremental algorithm to compute this diagram. The expected running time of this algorithm is O(n log n).

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

Pages (from-to) | 439-453 |

Number of pages | 15 |

Journal | Discrete and Computational Geometry |

Volume | 34 |

Issue number | 3 |

DOIs | |

State | Published - Sep 2005 |

Externally published | Yes |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics