0

DCEL が与えられた場合、最も近いサイトのペアを見つけるにはどうすればよいですか?

指定された DCEL がボロノイ図用であるとします。最も近いサイトのペアを見つけるにはどうすればよいですか? そして、時間の複雑さとは何ですか？

4

1 に答える 1

1

これを行う最も簡単な方法は、すべてのエッジを反復処理し、隣接する面を見つけ、ボロノイの中心間の距離を計算し、最小のペアを返すことです。DCEL 実装が、エッジを直接反復できないようなものである場合は、任意のグラフ トラバーサル アルゴリズム (深さ優先、幅優先など) を使用して反復を実行できます。

いずれにせよ、時間の複雑さは入力データ構造のサイズに比例します。

于 2012-09-24T19:56:06.093 に答える