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

[jlsk]

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

[helica]

量化后，线段树乱搞吧

[yangff]

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

[yangff]

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

[GtDzx]

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

[northisland]

图片搜索 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]

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

[rashawn]

预处理是啥意思…

[zagreb]

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

[artandlol]

傻比