Topology-oriented incremental algorithm for the robust construction of the Voronoi diagrams of disks.

摘要

Voronoi diagrams are important in many applications that range from theoretical computing to computational geometry, to computer graphics and computer vision. The relatively new problem of computing the Voronoi diagram for a set of geometry primitives with non-zero areas, rather than a set of points, is considerably more challenging. This paper deals with the case when the geometry primitives are a set of disks. Applications of these include pattern generation and circle packing.