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
相关阅读
统计专业,会C,想做数据分析,求职业规划.申请了H1B还可以再申请OPT吗？google intern怎么要面第三轮？请问做过面试官的，Java Developer/ Lead in NYC请问面试中small talk的问题电面遇到的问题amazon onsite 回来vmware这个公司怎样？【JOBS】招Software Engineer, QA, DBA at SF/NYCCS postdoc 进工业界还有戏不考大家个新题 visitor reconstruct generic tree大家intern或full time的工作都是有refer的吗？报Offer，求各位大侠给建议问一下 bloomberg的offer怎么减少人品损失庙小妖风大，破公司名堂多有没有在halliburton工作的朋友啊 software development方向cisco 硅谷招人求助，F1-H4-H1B，以前没有过H1B，什么时候可以开始工作？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。