论文部分内容阅读
在一个平面中有n个点,求解由这n点中任意3个点所组成的三角形中面积最小的三角形。很显然,可以简单地以穷举法计算出结果,但是,穷举法在这个问题的求解过程中的时间复杂度为O（n3）。提出一种基于Voronoi图的最小面积三角形的近似求解算法,其中时间复杂度是O（nlogn＋2n-5）。基本思想是分治法的思想,也就是把平面进行区域划分,把大问题转化成多个小问题来求解。