x**********g
发帖数: 91 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: xiabaitubing (大白兔), 信区: JobHunting
标 题: 请教一道题目！
发信站: BBS 未名空间站 (Fri May 14 13:48:23 2010, 美东)
谢谢！
在一个边长为1的正方形中，随机散落30个点，
每个点都有距离它最近的点，也就是neighbor,
求，这30个点中，哪个点与它的neighbor之间距离最远，哪个点于它的neighbor之间距
离最近，还
要算出30个点与neighbor之间距离的平均值。
不想计算出每个点与所有点之间的距离，不知道有没有更好的方法找每个点的neighbor。 | w***n
发帖数: 1084 | | x**********g
发帖数: 91 | 3 谢谢大牛！
我搜了一下KD tree,wiki上说
As a general rule, if the dimensionality is k, then number of points in
the data, N, should be N >> 2k. Otherwise, when kd-trees are used with
high-dimensional data, most of the points in the tree will be evaluated
and the efficiency is no better than exhaustive search. and approximate
nearest-neighbour methods are used instead.
意思就是不适合于high dimension的情况？
那我这个2维的，还是可以的噢。
【在 w***n 的大作中提到】
: Just make a kd tree.
| w***n
发帖数: 1084 | 4 Right. In 2D, you probably can just use a quad-tree, or a regular grid,
depending on how your points are distributed. | w***n
发帖数: 1084 | 5 Actually if just in 2D/3D, you probably can try a Delaunay triangulation too, and your nearest neighbor shouldn't be too far away from the neighborhood in the triangulation.
It is easy to prove that the nearest neighbor $B$ of $A$ should be in $A$'s neighborhood in the triangulation.
Because if it didn't, you can always find a triangle that is made of $A$ and its two neighbors containing $B$, which violates the Delaunay (voronoi) property. | l******e
发帖数: 470 | 6 你就 30个 点，直接算。。
有建kd树那个时间比这多的多的点都算完了
你要是3千3万个点再用其他数据结构吧。
neighbor。
【在 x**********g 的大作中提到】
: 谢谢大牛！
: 我搜了一下KD tree,wiki上说
: As a general rule, if the dimensionality is k, then number of points in
: the data, N, should be N >> 2k. Otherwise, when kd-trees are used with
: high-dimensional data, most of the points in the tree will be evaluated
: and the efficiency is no better than exhaustive search. and approximate
: nearest-neighbour methods are used instead.
: 意思就是不适合于high dimension的情况？
: 那我这个2维的，还是可以的噢。
|
|
