x**********g
发帖数: 91 | 1 谢谢！
在一个边长为1的正方形中，随机散落30个点，
每个点都有距离它最近的点，也就是neighbor,
求，这30个点中，哪个点与它的neighbor之间距离最远，哪个点于它的neighbor之间距
离最近，还
要算出30个点与neighbor之间距离的平均值。
不想计算出每个点与所有点之间的距离，不知道有没有更好的方法找每个点的neighbor。 |
x**********g
发帖数: 91 | 2 没有人回复吗？友情顶一下也行阿
neighbor。
【在 x**********g 的大作中提到】
: 谢谢！
: 在一个边长为1的正方形中，随机散落30个点，
: 每个点都有距离它最近的点，也就是neighbor,
: 求，这30个点中，哪个点与它的neighbor之间距离最远，哪个点于它的neighbor之间距
: 离最近，还
: 要算出30个点与neighbor之间距离的平均值。
: 不想计算出每个点与所有点之间的距离，不知道有没有更好的方法找每个点的neighbor。
|
b******v
发帖数: 1493 | 3 找出哪个点和它的neighbor最近，是closest pair的问题，可以有O(nlog(n))的解法
http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html
neighbor。
【在 x**********g 的大作中提到】
: 谢谢！
: 在一个边长为1的正方形中，随机散落30个点，
: 每个点都有距离它最近的点，也就是neighbor,
: 求，这30个点中，哪个点与它的neighbor之间距离最远，哪个点于它的neighbor之间距
: 离最近，还
: 要算出30个点与neighbor之间距离的平均值。
: 不想计算出每个点与所有点之间的距离，不知道有没有更好的方法找每个点的neighbor。
|
b******v
发帖数: 1493 | 4 每个点都求neighbor的话，感觉只能搞个两重循环来求了？这样是O(n^2)
之后再求最大值，最小值，平均值，都可以O(n)完成
neighbor。
【在 x**********g 的大作中提到】
: 谢谢！
: 在一个边长为1的正方形中，随机散落30个点，
: 每个点都有距离它最近的点，也就是neighbor,
: 求，这30个点中，哪个点与它的neighbor之间距离最远，哪个点于它的neighbor之间距
: 离最近，还
: 要算出30个点与neighbor之间距离的平均值。
: 不想计算出每个点与所有点之间的距离，不知道有没有更好的方法找每个点的neighbor。
|
x**********g
发帖数: 91 | 5 谢谢大牛回答问题。
那个closest pair我也看了，但是我要求每个点都求neighbor.
那个点都求neighbor，除了O（n^2)外，有没有再快一点的办法？
谢谢大牛！
【在 b******v 的大作中提到】
: 每个点都求neighbor的话，感觉只能搞个两重循环来求了？这样是O(n^2)
: 之后再求最大值，最小值，平均值，都可以O(n)完成
:
: neighbor。
|
b******v
发帖数: 1493 | 6 我是弱人一个，前面是抛砖引玉来着
期待真的大牛来解答这个问题
【在 x**********g 的大作中提到】
: 谢谢大牛回答问题。
: 那个closest pair我也看了，但是我要求每个点都求neighbor.
: 那个点都求neighbor，除了O（n^2)外，有没有再快一点的办法？
: 谢谢大牛！
|
x**********g
发帖数: 91 | 7 呵呵，同求！
【在 b******v 的大作中提到】
: 我是弱人一个，前面是抛砖引玉来着
: 期待真的大牛来解答这个问题
|
I*********g
发帖数: 93 | |
