一个基于Voronoi图的最小三角形的近似求解算法

摘要

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