中点有多少个点？

Question

给定一组坐标，我想知道如何确定有多少个点在另外两个点之间。

A(1 ; 3)
B(2 ; 2)
C(3 ; 1)
D(3 ; 2)
E(3 ; 3)

这里是一个图示：

_______
|A| |E|  
_______
| |B|D|  
_______
| | |C|  
_______

这里的B和D是中点，因此答案是“2”。

我找到了一个非常低效的O(n³)算法。

count := 0
For each point x1  
  For each point x2   
    For each point x3  
      If x3 is the midpoint of [x1;x2] 
        count := count + 1
Print count

你有没有想过更高效的算法？

- md5

Answer 1

使用k-d树，您可以将其改进为O(n^2 logn)：

将每个点存储在树中，并针对每对点（有O(n^2)个），搜索是否存在一个位于它们中间的点（易于计算中间点的位置）。每次查找是O(logn)，导致O(n^2 * log(n))的解决方案。

如果您只谈论整数，您可以通过将点放入哈希表（作为对）并检查是否存在具有所需坐标的元素，平均增加复杂度为O(n^2)。 （注意，这两个解决方案基本上相同，唯一的变化是集合的实现，一个使用树，另一个使用哈希表）。 伪代码：

set <- new set
for each point p:
   set.add(p)
for each point p1:
   for each point p2 != p1:
       candidate <- findMiddle(p1,p2)
       if set.contains(candidate):
           yield (p1,candidate,p2)

- amit