3

座標のリストを考えて、他の2つのポイントの真ん中にあるポイントの数を知る方法を知りたいです。

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

より効率的なアルゴリズムについて何か考えがありますか？

4

1 に答える 1

3

kdツリーを使用すると、次のように改善できますO(n^2 logn)。

ツリーに各ポイントを格納し、各ペア（それらがありますO(n^2)）について、それらの中央にポイントが存在するかどうかを検索します（中央がどこにあるかを計算するのは簡単です）。それぞれのシークは解決策をO(logn)もたらしO(n^2 * log(n))ます。

整数のみについて話している場合は、ポイントをハッシュテーブルに（ペアとして）配置し、目的の座標を持つ要素が存在するかどうかを確認することで、複雑さO(n^2)を平均的に高めることができます。

（2つのソリューションは基本的に同じであり、唯一のバリエーションはセットの実装であり、1つはツリーを使用し、もう1つはハッシュテーブルを使用することに注意してください）。

擬似コード：

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)
于 2013-01-10T19:19:32.707 に答える