Research On Properties Of Voronoi Diagram With Obstacles And Its Applications

Since 1990's, the Voronoi diagram has been applied in various fields. The Voronoi diagram has played an improtant role not only in the computational geometry, but also in many places in real life. It can be said that it is a very useful and important graphs.With the popularization and development of computer technology, Voronoi diagram applications range is expanding continually. In computational geometry, Voronoi diagram theory can be used to effectively solve the closest point search, the maximum empty circle, the smallest tree, and the convex hull of n plane points, etc. Voronoi diagram in common meaning takes euclidean distance as its measure, is a partition for the plane. This is a kind of ideal mode without considering obstacles.In order to expand applications fields of Voronoi diagrams, Voronoi diagram is expanded in this thesis. The main researches are put on the generating algorithm of Voronoi diagram with the obstacles and its applications. Beginning with the definition of Voronoi diagrams, the properties and generating algorithms of Voronoi diagrams are comprehensively summarized. Then a block partition algorithm of the plane, based on Voronoi diagrams, is proposed. With this algorithm, 2D or 3D space can be partitioned into periodic block fields, which has wide application values.Based on the comprehensive research Voronoi diagram, Voronoi diagram is extended to the case with obstacles. The Voronoi diagram with obstacles is defined. The Voronoi diagram of the obstacles in a city is defined, including city distance and obstacle city distance. The detailed researches on the various generating algorithms of Voronoi diagram were done. By comparing the advantages and disadvantages of various algorithms, good algorithm of generating oastacle Voronoi diagram is obtained. Finally the Voronoi diagram of the obstacle combined with the visibility graph effectively is applied to shortest path programming in obstacle enviroment. Visible Voronoi diagram algorthm is presented. The time complexity is O ( n2 logn) for any clearance value c, the effective path programing between any start point and goal point. The compution amount for analysing geometric graphs and preprocessing in the stage of searching is reduced.