p********y 发帖数: 111 | 1 如果已知这个连续点分布(各点间隔固定)中各点三维坐标,编程中最有效的方法求出
这个点分布的“最大直径”(不一定要非常精确)是哪一种? 谢谢
ps:我的设想,是x,y,z排序(只求最大值)后,构造一个大盒子囊括这个点分布,然
后中间切一刀把盒子分左右两半,然后左边每一个点对右边的每一个点求距离,然后对
这些距离求出最大值。虽然这样中间一刀可能刚好把两个最远点切到同一侧,但是对于
这个连续点分布来说应该不是大问题。 | a**********s 发帖数: 588 | 2 For an approximate approach, I would first fit the points with a line and
then compute the remost pair along the line. The time complexity is O(n)...
For exact solution, google three-dimensional diameter problem |
|