|
|||||
|
|
| 一个基于Voronoi图的最小三角形的近似求解算法 | |
| 引用本文： | 林加华,夏幼明.一个基于Voronoi图的最小三角形的近似求解算法[J].现代计算机,2009(12):58-60. |
| 作者姓名： | 林加华 夏幼明 |
| 作者单位： | 云南师范大学计算机科学与信息技术学院,昆明650092 |
| 摘 要： | 在一个平面中有n个点,求解由这n点中任意3个点所组成的三角形中面积最小的三角形。很显然,可以简单地以穷举法计算出结果,但是,穷举法在这个问题的求解过程中的时间复杂度为O（n3）。提出一种基于Voronoi图的最小面积三角形的近似求解算法,其中时间复杂度是O（nlogn＋2n-5）。基本思想是分治法的思想,也就是把平面进行区域划分,把大问题转化成多个小问题来求解。 |
| 关 键 词： | Voronoi图 近似求解 时间复杂度 最小三角形 分治法 |
An Approximation Solution Algorithm of the Smallest Triangle Based on Voronoi Diagram |
|
| Abstract: | |
| Keywords: | |
| 本文献已被 维普 万方数据 等数据库收录！ | |