An Algorithm for Generating Voronoi Diagram of 3D Scattered Point-set

An efficient algorithm for generating Voronoi diagram of 3D scattered point-set is proposed,which takes the data structure named "point-face-polyhedron" to store Voronoi cell,initializes the Voronoi cell of the first point,and the Voronoi cell of the new inserted point was generated after whose adjacent cells were changed accordingly through fission and reconstitution of cells.The experimental results show that this method can generate Voronoi diagram of 3D scattered point-set veraciously and efficiently.The topological neighbors inquiring for 3D scattered point-set can be realized efficiently based on this algorithm.