以代数曲线为边界的二维形体的Voronoi图

：Voronoi 图是计算几何中的重要概念之一。在计算机图形学、计算几何、有限元网格划分、机器人轨迹控制、模式识别、气象学和地质学研究中得到广泛应用，现有的二维Voronoi 图算法都是基于平面点集，多边形，或者以参数曲线为边界的二维形体的范围内解决的。由于代数曲线的难操作性，以代数曲线为边界的二维形体的Voronoi 图算法一直未得到解决。本文在区间分析和细分算法的基础上，提出了以代数曲线为边界的二维形体的Voronoi 图新算法。

在不同的领域， Voronoi 图有时也被称为Thiessen多边形、Dirichrit 网格、或Wigner-Seitz 域等。

Voronoi图的基本定义和算法可见于许多计算几何教科书。它是关于空间邻近关系一种基础数据结构。Voronoi 图有二维和三维、狭义和广义、一阶和高阶之分[1]。其中最基本、应用最广泛和研究最深入的还是二维欧氏 空间平面点集Voronoi 图，平面线集和面集Voronoi图可以通过平面点集Voronoi 图处理近似获得[2]。平面点集Voronoi 图常用构造算法主要包括矢量方法[3]和栅格方法，基于矢量的方法有增量构造算法、分治法、减量算法、平面扫描算法、间接法[1]；基于栅格的方法有邻域栅格扩张法和栅格邻近归属法[4,5]。

在矢量方法中，增量构造算法的时间复杂度为2O n，分