z**********g
发帖数: 209 | 1 Given a set of points (x,y) on a 2D coord system, identify list of 2D coords
that are of distance less than x units long.
Let x = 1;
Given (0,0), (0,1), (1, 2), (4,6);
Return 1 -> (0,0), (0,1)
brute force就是n^2了，carerrcup上讨论的结果就是这个题和 closest pair 不一样
，但是没什么结果 | M*m
发帖数: 141 | 2 x and y are both positive? | f*******e
发帖数: 1161 | 3 好像是可以先x(y)排序，大约类似一个sweep的算法，是n log n复杂度。有个论文讲这
个，也没读明白。
coords
【在 z**********g 的大作中提到】
: Given a set of points (x,y) on a 2D coord system, identify list of 2D coords
: that are of distance less than x units long.
: Let x = 1;
: Given (0,0), (0,1), (1, 2), (4,6);
: Return 1 -> (0,0), (0,1)
: brute force就是n^2了，carerrcup上讨论的结果就是这个题和 closest pair 不一样
: ，但是没什么结果
| g*****u
发帖数: 298 | | x******3
发帖数: 245 | 5 什么是KD tree， 给个全称吧，也好google
【在 g*****u 的大作中提到】
: KD tree?
| d*******d
发帖数: 2050 | 6 k-dimention tree.
【在 x******3 的大作中提到】
: 什么是KD tree， 给个全称吧，也好google
| K******g
发帖数: 1870 | 7 不明白，brute-force怎么回事N^2呢，我怎么觉得是N^N?
coords
【在 z**********g 的大作中提到】
: Given a set of points (x,y) on a 2D coord system, identify list of 2D coords
: that are of distance less than x units long.
: Let x = 1;
: Given (0,0), (0,1), (1, 2), (4,6);
: Return 1 -> (0,0), (0,1)
: brute force就是n^2了，carerrcup上讨论的结果就是这个题和 closest pair 不一样
: ，但是没什么结果
|
|
