Computing the Voronoi Diagram of a 3-D Polyhedron by Separate Computation of its Symbolic and Geometric Parts

摘要

The paper presents an algorithm to construct the Voronoi diagram of a 3-D linear polyhedron. The robustness and simplicity of the algorithm are due to the separation between the computation of the symbolic and geometric parts of the diagram. The symbolic part of the diagram, the Voronoi graph, is computed by a space subdivision algorithm. The computation of the Voronoi graph utilizes only relatively simple 2-D geometric computations. Given the Voronoi graph, and a geometric approximation given by the space subdivision, the construction of the geometric part is simple and reliable. An important advantage of the algorithm is that it enables local and partial computation of the Voronoi diagram. In a previous paper we have given a detailed proof of correctness of the computation of the Voronoi graph. This paper complements the previous one by detailing the algorithm and its implementation. In addition, this paper describes the computation of the geometric part of the diagram.