logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
KD Tree 找query点的最近点？
avatar
KD Tree 找query点的最近点？# JobHunting - 待字闺中
z*u
1 楼
用KDTree 在二维平面里来找某个query点附近最近的一点。请问如何处理这种特殊情况？
离query点x的最近的点*3在没有搜到的树杈上。因为从KDTree的root *1下来，会到左
半平面，它不会走到右半部分。
*1
*2 |
------------|
x | *3
avatar
a*8
2 楼
因为从KDTree的root *1下来，会到左
半平面，它不会走到右半部分。
你这步写错了
avatar
a*8
3 楼
第一步是计算query point到root1的距离，把它作为best_value,然后搜索root1的两边
,此时不能排除右边。
先搜左边，发现query point到root2的距离更小，update,但是并不能小于query point
到root1所划分的分割线，所有root1的右边还得接着搜（否则可以直接扔掉右边）
这样可以达到LogN的时间复杂度
avatar
z*u
4 楼
非常感谢 ：）

point

【在 a********8 的大作中提到】
: 第一步是计算query point到root1的距离，把它作为best_value,然后搜索root1的两边
: ,此时不能排除右边。
: 先搜左边，发现query point到root2的距离更小，update,但是并不能小于query point
: 到root1所划分的分割线，所有root1的右边还得接着搜（否则可以直接扔掉右边）
: 这样可以达到LogN的时间复杂度
avatar
z*u
5 楼
有个想法，可不可以把所有的点按找离hyperplane 的距离排序呢？ 比如说每个
hyperplane 有两个map之类。
不知道值不值的这样做，有没有更好的数据结构？

point

【在 a********8 的大作中提到】
: 第一步是计算query point到root1的距离，把它作为best_value,然后搜索root1的两边
: ,此时不能排除右边。
: 先搜左边，发现query point到root2的距离更小，update,但是并不能小于query point
: 到root1所划分的分割线，所有root1的右边还得接着搜（否则可以直接扔掉右边）
: 这样可以达到LogN的时间复杂度
avatar
o*h
6 楼
kd tree, segment tree, interval tree, 这些各种tree 有啥好的教材,易于面试实现
的？
求推荐

况？

【在 z***u 的大作中提到】
: 用KDTree 在二维平面里来找某个query点附近最近的一点。请问如何处理这种特殊情况？
: 离query点x的最近的点*3在没有搜到的树杈上。因为从KDTree的root *1下来，会到左
: 半平面，它不会走到右半部分。
: *1
: *2 |
: ------------|
: x | *3
相关阅读
入职前申请stem的opt延期有问题么面试别人的感受关于OPT到期在grace period期间转B2的问题请问：一般公司是否接受CPT for SUMMER INTERNSHIP?刚用offer push了一个公司两难选择，紧急情况，真心求助。Job opportunity_plant breeding第一份工作，C#还是Java区别大吗？ (转载)Amazon Tele Interview 感觉失败了 （转）去ONSITE的话，机票时间能长点吗Halliburton is hiring senior petrophysicist with shale experience.Does stem OPT extension qualify for h1-b cap-gap extension ????如何要求extend offer's deadline?求指教请问给一个整数，如何返回他的平方根？Amazon 电面, conference call 怎么用？急问：这种情况是out of status吗？面试要求做一个presentation恳求推荐data mining, statistical modelling 经典教材！！！Z今天上市了吗？唉，面试被cancel了
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。