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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2962 天前的主题，其中的信息可能已经有所发展或是发生改变。

给定 N 个基础点坐标(x,y)，求离指定点(px,py)最近的基础点
基础点可以预处理
要求时间复杂度<N

法题

基础

集思广益

给定

29 条回复 2017-10-26 20:45:06 +08:00

aheadlead

2017-09-04 19:30:19 +08:00

什么叫“基础点”

xiang578

2017-09-04 19:31:41 +08:00 via iPhone

不知道是不是 kd tree

GreatHumorist

2017-09-04 19:32:24 +08:00 via iPhone

向量计算公式？

Valyrian

2017-09-04 19:39:24 +08:00 via iPad

https://en.wikipedia.org/wiki/Voronoi_diagram

jlsk

2017-09-04 20:26:15 +08:00

@Valyrian 这个强，但是这个没法快速查找出来

@xiang578 应该就是它了，这能确实的<N 的时间查找出来，貌似还有更快的？

blahgeek

2017-09-04 21:12:21 +08:00 via iPhone

https://zh.m.wikipedia.org/zh-hans/最邻近搜索

lsmgeb89

2017-09-04 22:40:47 +08:00

这种算计算几何领域的算法？

yangff

2017-09-04 22:58:25 +08:00

@jlsk 这不都告诉你了用 voronoi 图了啊，O(NlogN)初始化，O(1)查询，还不是美滋滋

yangff

2017-09-04 22:59:06 +08:00

具体你可以看 voronoi 图的扫描线构造方法，反正你是一次性的。

ryd994

2017-09-04 23:31:11 +08:00 via Android

这也叫难？你想想手机基站的工作范围就可以想通了
剩下的是怎么把想法转化为算法

jedihy

2017-09-05 02:49:23 +08:00

google onsite 题，转换为极座标之后二分搜索

jedihy

2017-09-05 02:57:02 +08:00

@yangff 预处理不能给你这样预处理的，你这样我直接算距离初始化的时候 O(N)就全部做完了。
原题是说可以你可以选择给出的坐标的形式，然后让你找出距离最近的点。提示也很明显<O(N)，那就是 O(nlogn)了。

Xs0ul

2017-09-05 03:53:35 +08:00

@jedihy #11 能进一步解释一下极坐标的做法不？

Valyrian

2017-09-05 04:02:34 +08:00

@jedihy 预处理的时候没有 px, py 啊

jedihy

2017-09-05 04:48:38 +08:00

@Xs0ul 给我一点时间，去年准备 google onsite 的时候和同学讨论过，现在忘了，但思路我记得很清楚是极座标然后二分。

jedihy

2017-09-05 04:49:07 +08:00

@Valyrian 那这种方法是可行的，不过太高端了。

jlsk

2017-09-05 06:43:49 +08:00

@yangff
@Valyrian
@jedihy
怎么 O(1)时间查找出来啊？ voronoi 图虽然能画出来但是给定任意一个(px,py)你仍然不能确定它在哪个点的范围内，有立即求出的方法？

linux40

2017-09-05 07:34:23 +08:00 via Android

极坐标二分要用到极坐标下的距离公式吧。

messyidea

2017-09-05 08:17:45 +08:00

想来想去总感觉极坐标二分不了(
能想到一些杂七杂八预处理优化的办法, 但都能构造出在极端情况下退化到 O(N)的情况.
坐等正解

Valyrian

2017-09-05 08:17:51 +08:00 via iPad

@jlsk 查找是 O(log n)，plane subdivision： http://www.cs.cmu.edu/afs/cs/academic/class/15456-s10/ClassNotes/kirkpatrick.pdf

helica

2017-09-05 08:31:03 +08:00 via iPhone

量化后，线段树乱搞吧

yangff

2017-09-05 09:40:01 +08:00

@jlsk sweeping line 之后你就可以知道每个点属于 voronoi 图中的哪个区域了

yangff

2017-09-05 09:59:36 +08:00

hmm …… 如果你的 px, py 不是预先给出的话，查询是 logn 的
至于你可以用的各种算法你可以参考一下这本书…… 计算几何--算法与应用(第三版)

GtDzx

2017-09-05 10:11:35 +08:00

话说 google onsite 出这题的话是想听到什么回答呢？
我如果说我知道可以用 voronoi 图搞，但是具体怎么搞不会。是不是直接就跪了 -_-!!
要不然是可以先假设基础点分布比较随机，扯一扯 kd-tree/geohash 以及 google s2 库的实现？

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

2017-09-05 10:38:15 +08:00

http://www.cnblogs.com/LBSer/p/3310455.html

rashawn

2017-09-05 11:30:24 +08:00 via iPhone

预处理是啥意思…

zagreb

2017-09-05 12:12:37 +08:00 via iPhone

前几天不是有人发帖问“已知调色板中 N 个基本颜色，求任意颜色在调色板中最接近的颜色？”么。一个二位空间，一个 rgb 色彩空间。

artandlol

2017-10-26 20:45:06 +08:00 via Android

傻比