平面连通域VORONOI图的算法

AN ALGORITHM FOR THE VORONOI DIAGRAMS OF CONNECTED DOMAINS IN THE PLANE

摘要: 本文探讨了平面多边形的VORONOI图的性质，研究了通过合并多边形边界的两个子集生成平面单连通域VORONOI图的分治算法，以及合并外轮廓和“岛”轮廓的VORONOI图来生成平面多连通域VORONOI图的算法。

Abstract: In this paper the property of the Voronoi Diagram of a planar shape is studied and an algorithm for computing the Voronoi Diagrams of simply-connected and multiply-connected polygonal domains based on divide-and-conquer paradigm is presented.