Geometric relations among Voronoi diagrams

F. Aurenhammer and H. Imai


Two general classes of Voronoi diagrams are introduced and, along with their modifications to higher order, are shown to be geometrically related. This geometric background, on the one hand, serves to analyze the size and the combinatorial structure, and on the other hand, implies general and efficient methods of construction, for various important types of Voronoi diagrams considered in the literature.

Reference: F. Aurenhammer and H. Imai. Geometric relations among Voronoi diagrams. In Proc. $4^{th}$ Ann. STACS, Lecture Notes in Computer Science, volume 247, pages 53-65, Passau, Germany, 1987. Springer Verlag.