c**********e
发帖数: 2007 | 1 N points (x_i, y_i) in a 2-D plane. Find the smallest circle containing n
points. |
l******n
发帖数: 9344 | 2 http://en.wikipedia.org/wiki/Smallest_circle_problem
【在 c**********e 的大作中提到】
: N points (x_i, y_i) in a 2-D plane. Find the smallest circle containing n
: points.
|
c**********e
发帖数: 2007 | |
M****i
发帖数: 58 | 4 一个简单算法是在平面上随便找一点x_0作为初始迭代点，然后找到数据点中到x_0距离
最远的那个点y_0（这个点不唯一时随便取一个就行），然后从x_0出发沿着连接x_0和y
_0那条线段走一段距离t_0到达下一个迭代点x_1，然后重复以上步骤即可。可以证明，
当每次走的步长(t_k)_k所成的级数\sum_{k=0}^{\infty}t_k发散但是平方收敛时（比
方说可以取t_k=1/(k+1)）该算法最后收敛于数据点的minimax center。这个算法在黎
曼流形上也是成立的，只是步长与流形的曲率上界和下界有关。有兴趣的话可以看看下
面的文章：
http://hal.archives-ouvertes.fr/index.php?halsid=1ka58mlobsd187
【在 c**********e 的大作中提到】
: N points (x_i, y_i) in a 2-D plane. Find the smallest circle containing n
: points.
|
l******i
发帖数: 1404 | |
c**********e
发帖数: 2007 | 6 This is from somebody on this board's interview experience.
【在 l******i 的大作中提到】
: 会有这种面试题吗？回答起来没边了。。。。。
|
