平面内のポイントPのセットPの下部凸船体を効率的に計算するにはどうすればよいですか（r^2）？潜在的なアプローチをリストし、ランタイムの複雑さを分析します。
平面内の一連のポイントの凸型の船体を計算するいくつかのアルゴリズムがあり、ランタイムの複雑さと実装の容易さの観点から異なるトレードオフがあります。最も人気のあるもののいくつかは次のとおりです。

    Andrewのアルゴリズム：これは、X座標でポイントをソートし、モノトンチェーンを維持しながら左から右にポイントをスキャンするスイープラインアルゴリズムです。単調チェーンは、o（log n）時間がかかるバイナリ検索を使用して更新されます。ここで、nはチェーン内のポイント数です。アルゴリズムの全体的な時間の複雑さはO（n log n）です。

    Grahamのスキャン：これは、左端のポイントに対して極角でポイントをソートする別のスイープラインアルゴリズムです。次に、アルゴリズムはポイントを順番にスキャンし、非凸角を作成するとスタックからポイントを削除します。アルゴリズムの時間の複雑さはo（n log n）です。

    Chanのアルゴリズム：これは、グラハムのスキャンの改善であり、分裂と征服のアプローチを使用してポイントを極性角度で並べ替えます。アルゴリズムにはO（n log n）時間がかかり、Grahamのスキャンよりも優れた一定の因子を持っているため、大規模な入力で実際に速くなります。

    Jarvis March（ギフトラッピングとも呼ばれます）：これは、左端から始まり、現在の船体に最も近いポイントを繰り返し見つけるインクリメンタルアルゴリズムです。アルゴリズムは最悪の場合はO（n^2）時間がかかりますが、バイナリ検索ツリーを使用して最も近いポイントを見つけることでO（n log n）時間を取るように最適化できます。

    QuickHull：これは、極端なポイント（左端、右端、最上部、およびボットモストポイント）を見つけることから始まる分割統合アルゴリズムであり、その後、ポイントのセットを2つの凸面ハルに再帰的に分割します。アルゴリズムの時間の複雑さは、平均してO（n log n）、最悪の場合はo（n^2）です。

効率の観点から、最も効率的なアルゴリズムは、Andrew's、Graham's、Chanのものであり、O（n log n）の時間の複雑さがあります。Jarvis MarchとQuickhullアルゴリズムも実行可能なオプションですが、O（n^2）では、最悪の時間の複雑さが高くなります。