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

[jlsk]

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

[aheadlead]

什么叫“基础点”

[xiang578]

不知道是不是 kd tree

[GreatHumorist]

向量计算公式？

[Valyrian]

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

[jlsk]

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

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

[blahgeek]

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

[lsmgeb89]

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

[yangff]

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

[yangff]

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

[ryd994]

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

[jedihy]

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

[jedihy]

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

[Xs0ul]

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

[Valyrian]

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

[jedihy]

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

[jedihy]

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

[jlsk]

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

[linux40]

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

[messyidea]

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

[Valyrian]

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