n枚の円が与えられた時に, 交差する円のペアを全て列挙する. (ただし, 円の半径は異なってもよい)
Preparata & Shamosの本によると, 交差するペアの数をKとしたとき, 下界はΩ(n log n + K)になる. 現在僕が困っているのは, この最適なオーダーのアルゴリズムが知られているかどうかということ. この本には, 長方形の場合の最適なオーダーのアルゴリズムが紹介されている. また, 線分の場合はBalabanによって記憶量的にも最適なオーダーのアルゴリズムが提案されている.
ところが, 円の場合の最適なオーダーのアルゴリズムが見つからない. それっぽいキーワードでググっても, 別の問題の話ばかりなのだ. 仕方なく, 簡単なアルゴリズムを考えて実装してみた. 計算量はO(n^2)でナイーブな場合と変わらないけど, 実験では数倍早くなった. なんかめっちゃ地味なことしてるわ.
0 件のコメント:
コメントを投稿