基于分治法创建平面点集Voronoi图的研究

Creating Voronoi Diagram by Divide and Conquer Algorithm

Voronoi图被认为是最基本和最为重要的几何数据结构之一。主要研究用分治法构造Voronoi图，通过在双重连接边表的数据结构上作了一些改进。使数据结构的处理相对比较简单。并对多种特殊情况作了处理，使程序能够在多种情况下顺利的生成Vomnoi图。

Voronoi diagram is one of the most fundamental and important geometric data Structures, This paper is mainly research on creating V＇oronoi diagram by using Divide and Conquer Algorithm,by do some improving on the data structure of Double Connecting Edge List, we can deal with the data structure more simply. And we deal with many particular conditions so that the programme can create the Voronoi diagram favorably on most conditions.