Robust Construction of the Voronoi Diagram of a Polyhedron.
Victor Milenkovic · 1993
This paper describes a practical algorithm for the construction of the Voronoi diagram of a three dimensional polyhedron using approximate arithmetic. This algorithm is intended to be implemented in floating point arithmetic. The full two-dimensional version and significant portions of the three-dimensional version have been implemented and tested. The running time 1 of this algorithm is O(npnv log 2 b), where np is the size of the input polyhedron, nv is the size of the output Voronoi diagram, and b is the number of desired bits of precision. This algorithm can be made more practical with the use of a binary partition of space. In the worst case, binary partition does not improve the running time, but it should reduce the running time to O(nv b) on well-behaved inputs. Since b is constant, this eliminates a factor of np . The algorithm can be generalized to higher dimensions and the order k Voronoi diagram. 1 Introduction This author has been approached by researchers from comp...