Voronoi diagram for multiply-connected polygonal domains I: Algorithm

摘要

Voronoi diagrams of multiply-connected polygonal domains (polygons with holes) can be of use in computer-aided design. We describe a simple algorithm that computes such Voronoi diagrams in O(N(log2 N+H)) time, where N is the number of edges and H is the number of holes.