已知n个点坐标,求覆盖所有点的最小面积圆用什么算法?

来源：学生作业帮编辑：神马作文网作业帮分类：数学作业时间：2024/11/13 09:33:59

最简单的算法是任取三个点做一个圆,验证其他n-3个点是否在该圆内,并取遍所有的三个点的组合,记录其中最小的圆.这个算法的复杂度是O(n^4).
另一种较好的算法是Shamos提出的算法,复杂度是O(nlogn).
S1.计算点集S的凸壳CH(S)；
S2.计算CH(S)的直径,设为p[i]p[j],以p[i]p[j]为直径做圆C,如果S中的点都在圆C内,则C就是所求的最小覆盖圆；否则转S3；
S3.计算点集S的最远点意义下的Voronoi图即Vor(S)；
S4.设v是Vor(S)中的一个Voronoi点,以v为圆心,v至S点集中3个最远点的距离为半径做圆,该圆就是所求.
S1可以在O(nlogn)内完成,S2需要O(n)时间,S3需要O(nlogn)时间,S4的复杂度是O(n),所以整个算法的复杂度是O(nlogn).

有关时间复杂度的算法已知平面上N个点,使得在N个点组成的所有点对中,该店对间的距离最小.设计一个时间复杂度为0的算法. matlab已知30个点经纬度要求距离小于n的点连线,并求距离,求算法. 在已知n个点三维坐标的情况下,求每两点之间的距离.用matlab. 已知三点坐标求三角形面积已知三角形三点坐标求面积? 已知三点坐标,求三角形面积求N点坐标在平面坐标中,已知三点坐标,如何求三点所围的面积?（用行列式求）看一篇英文论文,提到：已知n个点的坐标,求一个点,到个点距离之和最近,首先是已知三个点,求一个点到三个点的距离和最近,他已知点A(-1,2),点B的坐标为(3,-1),在x轴上找一点P,使PA+PB的值最小,求点P的坐标. 已知点M(4,1),经过点M的直线L与x,y轴正半轴交于A,B,点O是坐标原点（1）如果三角形ABO面积最小,求直线设计一个算法,求已知三点的圆的方程的一个算法