今天GE牛在问这个问题，但是由于在工作就忽略了，后来是D大去回复的，
D大的思路如下：
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)。
 
感觉D大的方法有点小繁琐，我来谈谈自己的思路，首先如果我们从数学模型考虑，如果单纯考虑几个点的话，我们可以直接通过曲率半径求解的方法，果断计算出来，由于这个方法的普遍性，就不写详细的推导过程了，但是如果这个N是一些列的实验数据坐标点的话我们可以通过对应点做外接圆的方法来实现，只要分别求出所有3点组合覆盖的最小圆即可：

S1. 如果3点组成直角或钝角三角形，或3点共线，那么最小圆的半径就是三边中最长边的一半。

S2. 如果3点组成锐角三角形，最小圆为3点的外接圆我们很轻松的通过外接圆半径的计算方法求出半径

PS. 外接圆半径计算方法：

(a) 若3点构成一个三角形(即3点不共线)，并设3点的坐标为 (x1,y1)，(x2,y2)，(x3,y3)，求出两点(x1,y1)和(x2,y2)之间的距离L1=sqrt((x1-x2)^2+(y1-y2)^2), 同样求出(x1,y1)和(x3,y3)之间的距离L2，以及(x2,y2)和(x3,y3)之间的距离L3。

(b) 求出三角形半周长L=(L1+L2+L3)/2以及面积S=sqrt(L*(L-L1)*(L-L2)*(L-L3))。

(c) 根据公式4SR=L1*L2*L3，求外接圆半径R=L1*L2*L3/(4*S)。

3 对 “关于N点求最小半径的问题”的想法；

评论被关闭。