algorithm - 凸包を計算するギフト ワッピング アルゴリズム (Jarvis のアルゴリズム) の最悪のケースは何ですか?

Question

凸包を見つけるギフトラッピングアルゴリズムを実装するプログラムを作成しました。このアルゴリズムの最悪のケースとなるポイント セットを生成する方法はありますか?

そのようなケースをどのように生成しますか？

Answer 1

ポイントのセットがあるとします-S。反復ごとに、Sから1つのポイントを減算し、このポイントを凸包に追加すると、Sにまだ残っているすべてのポイントを確認する必要があります。

実行時間は出力のサイズに依存するため、Jarvis の行進は出力に依存するアルゴリズムです。

したがって、より大きな出力 - より多くの時間が必要です。そして、これは、それ自体が凸包であるセット上で実現できます。

おそらく、このような n ポイントの凸包を生成する最も簡単な方法は、すべてのポイントを円に配置することです。