w*5
2 楼
一个平面上n个点，需要两两配对，但有个constraint是距离不能大于k，这样有些点可
能最后无法被配对。有没有算法使得能配对的点最多？
follow-up是求出最小的k，使得所有点都能配上对。
这个应该怎么考虑？
能最后无法被配对。有没有算法使得能配对的点最多？
follow-up是求出最小的k，使得所有点都能配上对。
这个应该怎么考虑？
H*1
3 楼
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
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
4 楼
多谢大牛
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
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
5 楼
这是哪儿的面试题？
还是课程作业
【在 w********5 的大作中提到】
: 一个平面上n个点，需要两两配对，但有个constraint是距离不能大于k，这样有些点可
: 能最后无法被配对。有没有算法使得能配对的点最多？
: follow-up是求出最小的k，使得所有点都能配上对。
: 这个应该怎么考虑？
还是课程作业
【在 w********5 的大作中提到】
: 一个平面上n个点，需要两两配对，但有个constraint是距离不能大于k，这样有些点可
: 能最后无法被配对。有没有算法使得能配对的点最多？
: follow-up是求出最小的k，使得所有点都能配上对。
: 这个应该怎么考虑？
b*m
6 楼
奇数个点，多大的k也不行呀。
相关阅读
谷歌公布微软Windows操作系统重大漏洞，激怒微软。 zz求推荐machine learning credit risk modeling的书兼职机会for 数据科学方向（时薪：35-50美金）30岁转行data science如何求职招聘高薪IT,你想不成功都难有了其他专业的PhD，现读DS硕士，该如何写简历有同学注册了斯坦福的在线CS246--数据挖掘课程的吗？SQL DB Developer过渡到Data Science的可能性求教。大包子请教显卡选择问题Tuition Free data Scientist BootCamp fellowship【视频分享】大数据工程师必备知识 (转载)内推Google Optimal tier segementation怎么做？版面内和jobhunting的区别在？Nashville healthcare工作机会请教一个安装postgreSQL的问题【技术讲座】PASS Summit 2016 Recapdata analysis part time jobData Scientist Contract Position in Allstate寻找一起做一个自动交易系统 by Python