在 O(n log n) 时间内找到特殊点 k 的算法

Question

给算法一个 n log n 时间下界，以检查一组点是否有一个特殊点 k。

k 定义为:

for a set A of points, if for every point m in A, there is a point q in A such that k is in the middle of the line segment mq such a k does not have to belong to A.

例如，这个集合有一个特殊点 k = (0.5, 0.5) 用于一组四个点 (1,0), (0,1), (1,1), (0,0)。

当他们问我这个问题时，我完全面无表情，什么也没想到。我猜它需要一些强大的几何背景。

Answer 1

O(nlogn)解决方案(我仍然不清楚您为什么要寻找下限边界解决方案。您不妨做一个详尽的检查，然后运行一个 nlogn 循环来确保下限.不是很困难。我想你一定是指上界):

通过对所有点进行平均来找到唯一有效的候选点。 IE。将它们的坐标相加并除以点数。如果存在这样的 k，就是它。如果不存在这样的k，我们会发现在最后一步找到的点是无效的。

创建一个新的点数组(集)，我们在其中移动轴，使它们以点 k 为中心。 IE。如果k = (x_k,y_k)，一个点(x,y)将变成(x-x_k, y-y_{k )。根据比率 x/y 和范数 sqrt(x²+y²) 对点进行排序。正如下一步所示，如何进行排序并不重要，即哪个是主要标准，哪个是次要标准。}

我们可以搜索每个点的补集，或者更好的是，简单地遍历数组并验证每两个相邻点确实是补集。 IE。如果这是一个解决方案，那么这个新数组中的每两个互补点都是 (x,y) 和 (-x,-y) 的形式，因为我们重新居中了我们的轴，这意味着它们具有相同的比率(“梯度” ) 和范数，并且在排序之后，必须相邻。

如果 k 无效，那么我们将在此遍历中到达一个点，并发现它的邻居不是正确/互补形式 ==> 没有这样的 k。

时间=
O(n)寻找候选人 k +
O(n)用于构建新数组，因为每个新点都可以在 O(1) +
中计算 O(nlogn)对于排序 +
O(n)用于验证遍历
= O(nlogn)