在给定了一个圆以及N个确定点和一个在圆外的点M后，找到距离M最近的N个点中的那个点。时间复杂度为O(LogN)。

Question

http://www.glassdoor.com/Interview/Google-Interview-RVW2382108.htm

我已经尝试解决这个问题，但一直没有成功。请问有人可以给我提示如何继续解决这个问题。

我将使用两个点对的2条弦，即2个弦。找到它们的垂直平分线。使用这些平分线，我将找到圆的中心...

此外，我将提出圆的方程，并找到点M与圆的交点...那应该是最接近的点。然而，该点可能存在于N个点的集合中，也可能不存在。

谢谢。

- yuvi

---

这似乎是一个略微开放式的问题。面试者可能需要问一两个问题。那么你有什么想法呢？ - Beta

由于需要Log(N), 我感觉我应该能够在一次比较中丢掉至少一半的点。否则，我离问题的解决方案还差得远。 - yuvi

一个提示：考虑一条直线上的N个点和直线上的点M。是否有一个O(log(N))的解决方案？ - Beta

我可以尝试二分查找，但似乎不知道如何在这里应用它。 :( - yuvi

Answer 1

假设圆周上的点是“有序”的（即按照绕圆心的角度排序），您可以使用基于角度的二分搜索，这应该可以实现 O(log(n)) 的限制。

1. 从点 M 到圆心计算角度 A - O(1)。
2. 使用二分搜索找到圆周上最大角度小于 A 的点 I - O(log(n))。
3. 由于圆是凸的，最接近点 M 的点是 I 或 I+1。分别计算到两个点的距离，并取最小值 - O(1)。

- Darren Engwirda

---

我明白了。我之前认为我有一个反例，但是我错了，非常抱歉。 - yuvi

把数据按照θ排序不是需要O(n log n)的时间复杂度吗？（也许这个问题有误导性，我们实际上可以将其视为一次性成本，可以分摊到许多点M上。） - Gareth Rees

@GarethRees：是的，如果点最初是无序的，你需要对它们进行排序（这将是O(nlog(n))）。我假设点是按顺序给出的。由于这是一个面试问题，我认为你可能会在当时与他们讨论这些想法... - Darren Engwirda

Answer 2

要找到距离M最近的点，我们需要基于平面切割进行二分消除点。在预处理输入点后，我们可以在O(lgn)时间内找到任何给定点M的最近点。

1. 计算（如果没有给出）点的极坐标表示形式（r，θ格式），其中r是距离中心的距离，θ是x轴上的角度范围为（-180,180]。 2. 按照它们相对于x轴的角度递增的顺序对所有N个点进行排序。

请注意，简单的二分查找最接近M的点在这里不起作用，例如，

如果给定的点按θ =（-130，-100，-90，-23，-15，0，2，14，170）排序，则对于θ = -170的点M，二分搜索将给出-130（40度之远）作为最接近的点，而170（20度之远）是最接近M的点。

如果我们在排序时忽略符号（认为这将产生正确的输出），则我们的新排序数组看起来像θ =（0,2,14,15,23,90,100,130,170），对于θ = -6的点M，二分搜索将得出结果应该是2或14，而在这种情况下，0是最接近M的点。

要使用平面切割执行搜索操作，请执行以下操作：

1. 找到通过圆心并垂直于连接圆心与点M的线的平面切割线。 2. 消除圆形平面的一半[90 +θ，-90 +θ）或[-90 +θ，90 +θ），具体取决于M位于哪个半平面中。 3. 进行与第一次切割平行且通过前一个平面中间的点的平面切割，并消除较远离M的半平面中的所有点，直到在较近的半平面中没有点为止，在这种情况下，消除较近的半平面。 4. 不断切割平面，直到只剩下一个点。那个点是最接近M的点。总操作需要O（lgn）步。

如果数据偏斜且在圆中不均匀分布，则可以优化我们的平面切割，使每个切割通过剩余搜索操作中角度的中位数。

- Faraz