＜集大成＞アルゴリズム大辞典

＜集大成＞アルゴリズム大辞典 at TECH

470:デフォルトの名無しさん
08/09/19 01:27:09
>>468
動的ボロノイ図を使えば，一反復が O(n + k log n) でできる．
ただし k は引き離す必要のあるペアの数．

ただ，これは実装が結構しんどいので，現実的には
x 座標でソートしたリストを盛っておいて，x 座標の近い順に見て
枝刈りするのが有力だと思う
（x 座標が一定距離を超えたら，距離が一定距離以下にはならない等）
計算量は最悪 O(n^2) だから変わってないけれど，現実的には改善されるはず．

なお，ソートは最初の一回だけ行えば，あとは引き離したところだけ更新すると
多少の効率化ができる．

次ページ

続きを表示

1を表示