The Generation And Application Of Higher-Dimensional Voronoi Diagram

Voronoi diagram is an important research area in computational geometry. It has been broadly applied to many fields such as computer graphic, CAD, GIS, spatial neighborhood analysis, path planning, and virtual reality.There are many researches on 2 or 3 dimensional algorithm of Voronoi diagram generation. But in higher dimension, there are few achievements due to the increased complexity. This paper leverages the relationship between Voronoi diagram, Delaunay triangulation and convex hull, studies and improves at higher-dimensional algorithms of convex hull and applies it to generate higher-dimensional Voronoi diagram. This paper introduces current algorithms and studies their time complexities. Then focuses on Quickhull algorithm and brings some improvements. On the efficiency of the algorithm, this paper brings two improvements. One is to improve its data structure to speed up searching. Two is to design a mechanism for parallel execution. On the the robustness of the algorithm also brings two improvements. First is to deal with the degradation of points set. Second is self-checking method to ensure the result is correct.Due to its excellent properties, Voronoi diagram is widely applied in many fields such as path planning, higher-dimensional cluster analysis, etc. It also has some cross-field applications, such as combinations with physics, chemistry, biology, machinery manufacturing, and mobile communications.! With the continuous expansion of higher-dimensional Voronoi diagram application requirements, this paper has a good theoretical and practical significance.