找最近的点，这题咋解？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

找最近的点，这题咋解？

找最近的点，这题咋解？# JobHunting - 待字闺中

h*g2012-04-07 07:04

1 楼

You are given a list of points in the plane, write a program that
outputs each point along with the point that are closest
to it.
The order is less then O(n^2) .
For example, given a set of points where each line is of the form:
ID x-coordinate y-coordinate
1 0.0 0.0
2 10.1 -10.1
3 -12.2 12.2
4 38.3 38.3
5 79.99 179.99
Your program should output:
1 2
2 1
3 1
4 1
5 4

l*82012-04-07 07:04

2 楼

如果要求O(n^2), 那么最naive办法都可以了。
如果要快些的话，好像可以用Quad-tree.

【在 h*****g 的大作中提到】

: You are given a list of points in the plane, write a program that
: outputs each point along with the point that are closest
: to it.
: The order is less then O(n^2) .
: For example, given a set of points where each line is of the form:
: ID x-coordinate y-coordinate
: 1 0.0 0.0
: 2 10.1 -10.1
: 3 -12.2 12.2
: 4 38.3 38.3

h*g2012-04-07 07:04

3 楼

我看到一种 nlogn 的解法，但感觉不对。。
Approach:
First Have all the points in an array and sort them according to their X
axis, which would give:
3 -12.2 12.2
1 0.0 0.0
2 10.1 -10.1
4 38.3 38.3
5 79.99 179.99
Then for every point P, calculate the distance from 1 point in the front and
1 point in the back:
For Ex: Point with Id=3 (-12.2, 12.2) does not have 1 point
in the back.
Always store only min distance and the corresponding point Ids
Then Sort the points according to their Y Axis, which would give:
2 10.1 -10.1
1 0.0 0.0
3 -12.2 12.2
4 38.3 38.3
5 79.99 179.99
然后 do the same procedure as X 坐标。
Total complexity: 2nlogn + 4kn + klogk = O(nlogn)
k = 1 here.

【在 l*********8 的大作中提到】

: 如果要求O(n^2), 那么最naive办法都可以了。
: 如果要快些的话，好像可以用Quad-tree.

d*o2012-04-07 07:04

4 楼

你总要计算任意两个pair之间的值吧，这样就是O(n^2)
如果比上面的要小，倒是可以计算任意点到原点的距离，排序一下，排除所有与该点距
离之差大于与最小距离之和的点，然后再找最小距离点，不过最坏情况也是O(n^2)

f*i2012-04-07 07:04

5 楼

K-d tree? nlgn.

l*i2012-04-07 07:04

6 楼

Jon Bentley's phd dissertation from UNC has the solution. Honestly it is way
too difficult for an interview. the problem is called all pair nearest
neighbor or simply All NN. Facebook puzzle used to have such a problem but
for that one you can get Accepted by some pruning in search.