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

Question

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

- user2311963

---

亲爱的维克拉姆，我们在d维空间中使用Kd树进行范围搜索。 Kd树与我的问题无关。谢谢。 - user2311963

你是说查询行是指 y = mx + c 吗？ - Vikram Bhat

请问您能否解释一下如何实现，或者提供一些思路。据我所知，我们可以使用kd树来查找距离给定输入点最近的点。在我的情况下，查询线（y = mx + c）已经给出。 - user2311963

什么是查询语句？ - Lajos Arpad

@Lajos 输入了一些形如 y = mx + c 的代码行。 - user2311963

在这种情况下，你所说的二元性是什么意思？ - Ante

Answer 1

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

考虑旋转后的站点的排序横坐标：通过二分法可以找到最靠近垂直线的站点，需要进行Lg(N)次比较。

现在考虑连续的旋转集合：可以将其划分为角度范围，使得排序后的横坐标顺序不发生改变。

因此，您将通过取成对的站点来找到所有极限角度，并存储角度值以及旋转后的横坐标的对应顺序。

对于查询，首先进行第一次二分搜索（在O(N²)个角度中），找到包含角度间隔，然后在旋转后的横坐标上进行搜索（在O(N)个横坐标中进行二分搜索），找到最接近的站点。

按照直接的方式实现，这将需要O(N³)的存储空间。

考虑到两个连续角度的排序排列只有一个交换不同，使用适当的数据结构，可以想象可以实现O(N²)的存储空间。

- user1196549

Answer 2

对于点(xi,yi)，其到直线的距离为d = |yi-mxi-c|/sqrt(1+m^2)。

我们需要最小化f(x,y) = (y-mx-c)^2

这些是关于(m,c)的二次方程。

满足条件：

F(xi,yi) <= F(x1,y1),F(x2,y2)..

假设您得到了一个解算器，那么您将获得满足条件的（m，c）区间。

您可以使用区间树来搜索线段（m，c）所在的区间和点。

- Vikram Bhat

---

区间没有“好看”的形状，对于一个点来说，有更多的区间是它最近的点。 - Ante

@Ante 无论形状如何，区间树都可以将它们排列，以便在O(logN)时间内进行搜索，尽管无法保证有多少个区间。 - Vikram Bhat

Answer 3

你需要找到经过点 I 且垂直于该线的直线。然后解出这两条直线的方程组，得到交点。这是离初始线最近的点，但不一定在 S 中。我们称交点为 I'。如果你的 S 元素按照 x 排序，那么你可以通过二分搜索获取最靠近 I'.x 的 S 中的 x，并返回具有该 x 值的点。

- Lajos Arpad

Answer 4

你不必直接用二元性来表述，但关键观察是对于两个点，更靠近一个点的线与另一个点的线之间的边界是满足某些斜率和截距不等式的线集。因此，如果使用这些不等式，那么从某种意义上讲，无论做什么，都将线视为“点”（一对满足某些不等式的数字，以找到最近的点）。似乎唯一的其他选择是进行一些预处理，以便快速找到点在任意给定线上的最近投影（例如通过计算少量投影并消除其余考虑），但这似乎难以保证每个查询线的O(log n)时间运行。

- user2566092

Answer 5

这应该可以工作：

通过将所有点投影到旋转扫描线上，并记录投影点的扫描线角度theta和参数，从0到pi的角度进行预处理。每当两个点重合时，即“交叉”，就执行一次此操作。在这里，“参数”是指选择任何固定原点A，并为所有p记录（p-A）点积[cos theta，sin theta]。将有O（n ^ 2）个这些扫描线记录，因此可以按角度在O（log n）时间内搜索它们。给定查询线Q，请使用二分搜索找到两个记录的扫描线，以角度括住Q的垂线。记录的投影具有与在Q的垂线上投影的点的顺序相同的点的顺序。现在找到点R的参数，它是Q在其自己的垂线上通过A投影的点。在括号扫描线中再使用一次二分搜索，以找到最靠近B的点。这是距离Q最近的点。

- Gene