现代计算机（专业版）
現代計算機（專業版）
현대계산궤（전업판）
MODERN COMPUTER
2009年
12期
58-60
,共3页
Voronoi图%近似求解%时间复杂度%最小三角形%分治法
Voronoi圖%近似求解%時間複雜度%最小三角形%分治法
Voronoi도%근사구해%시간복잡도%최소삼각형%분치법
在一个平面中有n个点,求解由这n点中任意3个点所组成的三角形中面积最小的三角形.很显然,可以简单地以穷举法计算出结果,但是,穷举法在这个问题的求解过程中的时间复杂度为O(n3).提出一种基于Voronoi图的最小面积三角形的近似求解算法,其中时阍复杂度是O(nlogn+2n-5).基本思想是分治法的思想,也就是把平面进行区域划分,把大问题转化成多个小问题来求解.
在一箇平麵中有n箇點,求解由這n點中任意3箇點所組成的三角形中麵積最小的三角形.很顯然,可以簡單地以窮舉法計算齣結果,但是,窮舉法在這箇問題的求解過程中的時間複雜度為O(n3).提齣一種基于Voronoi圖的最小麵積三角形的近似求解算法,其中時閽複雜度是O(nlogn+2n-5).基本思想是分治法的思想,也就是把平麵進行區域劃分,把大問題轉化成多箇小問題來求解.
재일개평면중유n개점,구해유저n점중임의3개점소조성적삼각형중면적최소적삼각형.흔현연,가이간단지이궁거법계산출결과,단시,궁거법재저개문제적구해과정중적시간복잡도위O(n3).제출일충기우Voronoi도적최소면적삼각형적근사구해산법,기중시혼복잡도시O(nlogn+2n-5).기본사상시분치법적사상,야취시파평면진행구역화분,파대문제전화성다개소문제래구해.
