| 平面上两个点集间距离的O(nlogn)算法 |
| |
| 引用本文： | 方剑英,杜智华.平面上两个点集间距离的O(nlogn)算法[J].新疆大学学报(理工版),2003,20(3):236-238. |
| |
| 作者姓名： | 方剑英 杜智华 |
| |
| 作者单位： | 新疆师范大学数理信息学院，新疆乌鲁木齐,830054 |
| |
| 摘 要： | 定理“平面上两个点集的距离所在边是Voronoi图的Delaunay三角剖分中一条边”是本文的核心。在该定理基础上，本文提出如何用Voronoi图的Delaunay三角剖分算法求平面上两个点集的距离．并分析其复杂性．
|
| 关 键 词： | 点集 距离 O（nlogn）算法 Voronoi图 Delaunay三角剖分 时间复杂度 计算机图形学 |
| 文章编号： | 1000-2839(2003)03-0236-03 |
| 修稿时间： | 2003年5月7日 |
An O(nlogn) Algorithm for the Shortest Paths between Two Set of Points in the Plane |
| |
| Abstract: | 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. |
| |
| Keywords: | convex hull Voronoi diagrams Delaunay triangulations the nearest neighbor problem minimum weight triangulations |
| 本文献已被 CNKI 维普 等数据库收录！ |
