平面上两个点集间距离的O(nlogn)算法

An O(nlogn) Algorithm for the Shortest Paths between Two Set of Points in the Plane

定理"平面上两个点集的距离所在边是Voronoi图的Delaunay三角剖分中一条边"是本文的核心,在该定理基础上,本文提出如何用Voronoi图的Delaunay三角剖分算法求平面上两个点集的距离,并分析其复杂性.

The theorem that the edge on which the distance between two set of points in the plane decides is one of the edges of the Voronoi disgrams's Delaunay triangulations is the key of this paper. On the basis of this theorem,the paper proposes how to compute the distance between two set of points in the plane by means of Voronoi dasgrams's Delaunay triangulations.Moreover,it also analyzes the complexity of the algorithm.