algorithm - 如何在不使用对偶概念的情况下，在 O(log n) 时间内从一组点中找到距给定查询线最近的点？

Question

假设我们得到了一个包含 n 个点的集合 S 和一条任意查询线 l。做一些预处理(对偶性除外)，以便我们可以在 O(log n) 时间内(对空间没有限制)回答最接近(S)的点到 l。

Answer 1

你说“对空间没有限制”，这意味着对预处理时间没有限制。

考虑旋转任意角度后站点的排序横坐标:经过 Lg(N) 比较后，通过二分法找到最接近垂直线的站点。

现在考虑连续的旋转集:您可以将其划分为角度范围，这样排序的横坐标的顺序就不会改变。

所以你会通过成对的站点找到所有的极限角度，并存储角度值以及旋转横坐标的相应顺序。

对于查询，首先通过二分搜索(在 O(N²) 个角中)找到封闭角度区间，然后通过在旋转的横坐标上搜索(在 O(N) 个横坐标中二分搜索)找到最近的站点。

以直接的方式完成，这将需要 O(N³) 存储。

鉴于两个连续角度的排序排列仅相差一次交换，通过合适的数据结构可以实现 O(N²) 存储并不是不可想象的。