w********5
发帖数: 54 | 1 一个平面上n个点，需要两两配对，但有个constraint是距离不能大于k，这样有些点可
能最后无法被配对。有没有算法使得能配对的点最多？
follow-up是求出最小的k，使得所有点都能配上对。
这个应该怎么考虑？ | H*******1
发帖数: 242 | 2 G(V,E) where |V| = n as points, E = {(u,v)| dist(u,v) <= k}
Now what you are looking at are matchings, so just apply Edmonds' algorithm.
O(\sqrt(V) * E). Since the G is a unit disk graph here, you may be able to
improve the algorithm, google or wait till DaNiu post an answer.
For finding the smallest k, there are probably smarter ways, but a 糙快猛
practical solution could be:
Find d = closest pair distance O(nlgn)
Find D = farthest pair distance O(nlgn)
Binary Search on [d, D] O(lg(D-d) * \sqrt(V) * E) until you find the k | w********5
发帖数: 54 | 3 多谢大牛
algorithm.
【在 H*******1 的大作中提到】
: G(V,E) where |V| = n as points, E = {(u,v)| dist(u,v) <= k}
: Now what you are looking at are matchings, so just apply Edmonds' algorithm.
: O(\sqrt(V) * E). Since the G is a unit disk graph here, you may be able to
: improve the algorithm, google or wait till DaNiu post an answer.
: For finding the smallest k, there are probably smarter ways, but a 糙快猛
: practical solution could be:
: Find d = closest pair distance O(nlgn)
: Find D = farthest pair distance O(nlgn)
: Binary Search on [d, D] O(lg(D-d) * \sqrt(V) * E) until you find the k
| l******n
发帖数: 648 | 4 这是哪儿的面试题？
还是课程作业
【在 w********5 的大作中提到】
: 一个平面上n个点，需要两两配对，但有个constraint是距离不能大于k，这样有些点可
: 能最后无法被配对。有没有算法使得能配对的点最多？
: follow-up是求出最小的k，使得所有点都能配上对。
: 这个应该怎么考虑？
| b******m
发帖数: 382 | |
|
