凸包を計算するギフト・ウェッティング・アルゴリズム（Jarvis's Algorithm）の最悪のケースは何ですか？

Question

私は凸包を見つけるGift Wrappingアルゴリズムを実装するプログラムを作っています。このアルゴリズムの最悪の場合として機能するポイントセットを生成する方法はありますか？

このようなケースはどのように生成されますか？あなたはSから1ポイントを引くと凸包にこの点を追加すると、すべての繰り返しでS.、あなたはまだS.

に残って何すべての点を確認する必要がある -

Answer 1

あなたは点の集合を持っていると仮定します実行時間は出力のサイズに依存するため、Jarvisのmarchは出力に敏感なアルゴリズムです。

出力が大きいほど、より多くの時間が必要です。そして、これは、それ自身の凸包であるセットで達成することができます。

おそらく、nのこのような凸包を生成する最も単純な方法は、すべての点を円上に置くことを指します。