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
相关阅读
刷POJ不如刷ML吧？等facebook等得心焦Apple的马工值得去面么【招聘】chemist想当年我八神的无限鬼步+屑风 还是赢得了众多小伙伴心目中的地位。为什么到现在版上才有人开始讨论刷题o基础 可以刷题么我来说一下我朋友遇到的倒霉事 (转载)现在大部分的公司找人都说微软现在onsite还是见到最后一轮manager就基本有希望，如果fail直接中间就送走？请问街霸哥，如果包裹已经达到40万。请教一个ES问题。多谢！谁知道Homeaway这家公司怎么样大家买擦电脑显示屏的专用纸从哪里买？现在公民cs master 都不好找工作嗎？IT certification vs degree vs 刷题刷poj有人拿到40万的告诉我一声【长期提供推荐】Poynt, 多个职位， 软件硬件都有IT公司不管饭是不是硬伤?7位数年薪(美元)的80后程序员的生活
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。