V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
jlsk
V2EX  ›  问与答

新听到一个超难算法题,大家来集思广益

  •  
  •   jlsk · 2017-09-04 18:57:05 +08:00 · 4864 次点击
    这是一个创建于 2666 天前的主题,其中的信息可能已经有所发展或是发生改变。
    给定 N 个基础点坐标(x,y),求离指定点(px,py)最近的基础点
    基础点可以预处理
    要求时间复杂度<N
    29 条回复    2017-10-26 20:45:06 +08:00
    aheadlead
        1
    aheadlead  
       2017-09-04 19:30:19 +08:00
    什么叫“基础点”
    xiang578
        2
    xiang578  
       2017-09-04 19:31:41 +08:00 via iPhone
    不知道是不是 kd tree
    GreatHumorist
        3
    GreatHumorist  
       2017-09-04 19:32:24 +08:00 via iPhone
    向量计算公式?
    Valyrian
        4
    Valyrian  
       2017-09-04 19:39:24 +08:00 via iPad   ❤️ 1
    jlsk
        5
    jlsk  
    OP
       2017-09-04 20:26:15 +08:00
    @Valyrian 这个强,但是这个没法快速查找出来

    @xiang578 应该就是它了,这能确实的<N 的时间查找出来,貌似还有更快的?
    blahgeek
        6
    blahgeek  
       2017-09-04 21:12:21 +08:00 via iPhone
    lsmgeb89
        7
    lsmgeb89  
       2017-09-04 22:40:47 +08:00
    这种算计算几何领域的算法?
    yangff
        8
    yangff  
       2017-09-04 22:58:25 +08:00
    @jlsk 这不都告诉你了用 voronoi 图了啊,O(NlogN)初始化,O(1)查询,还不是美滋滋
    yangff
        9
    yangff  
       2017-09-04 22:59:06 +08:00
    具体你可以看 voronoi 图的扫描线构造方法,反正你是一次性的。
    ryd994
        10
    ryd994  
       2017-09-04 23:31:11 +08:00 via Android
    这也叫难?你想想手机基站的工作范围就可以想通了
    剩下的是怎么把想法转化为算法
    jedihy
        11
    jedihy  
       2017-09-05 02:49:23 +08:00
    google onsite 题,转换为极座标之后二分搜索
    jedihy
        12
    jedihy  
       2017-09-05 02:57:02 +08:00
    @yangff 预处理不能给你这样预处理的,你这样我直接算距离初始化的时候 O(N)就全部做完了。
    原题是说可以你可以选择给出的坐标的形式,然后让你找出距离最近的点。提示也很明显<O(N),那就是 O(nlogn)了。
    Xs0ul
        13
    Xs0ul  
       2017-09-05 03:53:35 +08:00
    @jedihy #11 能进一步解释一下极坐标的做法不?
    Valyrian
        14
    Valyrian  
       2017-09-05 04:02:34 +08:00
    @jedihy 预处理的时候没有 px, py 啊
    jedihy
        15
    jedihy  
       2017-09-05 04:48:38 +08:00
    @Xs0ul 给我一点时间,去年准备 google onsite 的时候和同学讨论过,现在忘了,但思路我记得很清楚是极座标然后二分。
    jedihy
        16
    jedihy  
       2017-09-05 04:49:07 +08:00
    @Valyrian 那这种方法是可行的,不过太高端了。
    jlsk
        17
    jlsk  
    OP
       2017-09-05 06:43:49 +08:00
    @yangff
    @Valyrian
    @jedihy
    怎么 O(1)时间查找出来啊? voronoi 图虽然能画出来但是给定任意一个(px,py)你仍然不能确定它在哪个点的范围内,有立即求出的方法?
    linux40
        18
    linux40  
       2017-09-05 07:34:23 +08:00 via Android
    极坐标二分要用到极坐标下的距离公式吧。
    messyidea
        19
    messyidea  
       2017-09-05 08:17:45 +08:00
    想来想去总感觉极坐标二分不了(
    能想到一些杂七杂八预处理优化的办法, 但都能构造出在极端情况下退化到 O(N)的情况.
    坐等正解
    Valyrian
        20
    Valyrian  
       2017-09-05 08:17:51 +08:00 via iPad
    helica
        21
    helica  
       2017-09-05 08:31:03 +08:00 via iPhone
    量化后,线段树乱搞吧
    yangff
        22
    yangff  
       2017-09-05 09:40:01 +08:00
    @jlsk sweeping line 之后你就可以知道每个点属于 voronoi 图中的哪个区域了
    yangff
        23
    yangff  
       2017-09-05 09:59:36 +08:00
    hmm …… 如果你的 px, py 不是预先给出的话,查询是 logn 的
    至于你可以用的各种算法你可以参考一下这本书…… 计算几何--算法与应用(第三版)
    GtDzx
        24
    GtDzx  
       2017-09-05 10:11:35 +08:00
    话说 google onsite 出这题的话是想听到什么回答呢?
    我如果说我知道可以用 voronoi 图搞,但是具体怎么搞不会。是不是直接就跪了 -_-!!
    要不然是可以先假设基础点分布比较随机,扯一扯 kd-tree/geohash 以及 google s2 库的实现?
    northisland
        25
    northisland  
       2017-09-05 10:21:53 +08:00
    图片搜索 CBIR,或者图片配准中,的最基础问题了。
    属于暴力搜索的近似问题,

    现在最流行 Optimized Product Quantization 和 Product Quantization Tree。之前的 FLANN ( kd-Trees 和 K-Mean Trees 结合)也很经典。

    https://github.com/yahoo/lopq
    https://github.com/cgtuebingen/Product-Quantization-Tree

    那都是高维数据的玩法,这就是二维。
    1djmao
        26
    1djmao  
       2017-09-05 10:38:15 +08:00
    rashawn
        27
    rashawn  
       2017-09-05 11:30:24 +08:00 via iPhone
    预处理是啥意思…
    zagreb
        28
    zagreb  
       2017-09-05 12:12:37 +08:00 via iPhone
    前几天不是有人发帖问“已知调色板中 N 个基本颜色,求任意颜色在调色板中最接近的颜色?”么。一个二位空间,一个 rgb 色彩空间。
    artandlol
        29
    artandlol  
       2017-10-26 20:45:06 +08:00 via Android
    傻比
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2903 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 13:49 · PVG 21:49 · LAX 05:49 · JFK 08:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.