High Dimensional Voronoi Algorithm Research

Voronoi diagram is an important problem of computational geometry, and have important applications in many fields. Voronoi diagram is that it has many excellent properties, including nearest neighbors, the control region. These excellent properties make it widely used in 2 d and 3 d space domain, including GIS, data index, motion planning, urban planning, etc.Voronoi algorithm of planar point has main effective algorithm, like growth algorithm, incremental algorithm, divide and conquer algorithm, and the sweep line algorithm., and approximate algorithms which are based on raster and distance transformation technology. High dimensional Voronoi diagram directly computation is not as easy as plane Voronoi diagram. So research in this paper is all about high dimensional Voronoi. Commonly we use the indirect method, such as the use of dual Delaunay graph, the use of more high dimensional convex hull or half space insection. This paper expounds and proves the relationships amongs Voronoi diagram and the three others, and introduces some higher dimensional Delaunay algorithms, higher dimensional convex hull algorithms, high dimensional half space intersection algorithms.This paper discus the implementation detail of the increamental insert algorithm of the high dimension Delaunay and puts forward solutions to solve th problems, such as the calculation of circumcenter of hyper circumsphere method. We mainly focus on the "conflict simplexes search" of the increamental insert Delaunay algorithm. Also the paper expounds multiple optimal solutions for the confict simplex search problem, including 1) using adjacency relations and the breadth-first search strategy,2) index base on the history simplex, aka Delaunay Tree,3) index base on uniform grid,4) index base on dynamic Quadtree,5) index base on common vertice of simplexes. The peripheral storage optimization scheme is put forward, solving the problem of insufficient memory when applying to the higher dimensional calculation and solving requirement of persistent of the the result triangulation.At last of this paper performance bench experiments were carried to compared the programs implemented by author, which include the high-dimensional Watson algorithm and the high dimensional DeWall algorithm, with existing of higher dimensional Delaunay triangulation programs included the well used computational geometry libraries. The experimental data show that the optimizations issued in this paper is good, peripheral storage optimization scheme make the program use less memory but handle for larger amount of data.