速い船体アルゴリズムで凸包を計算する

Question

私は計算幾何学を学んでおり、凸包を計算するための速い船体アルゴリズムのトピックを学び始めました。私は質問があります。 アルゴリズムが最悪の場合の時間の複雑さを持つ2D点の集合（例えば10点）を描きたいのですが、どうすればできますか？ポイントがどんなものかを見つけるための簡単な方法はありますか？私は拒絶がこれまでに発生していないときQuickHullの最悪のケースであることを推測

迅速な船体アルゴリズムの擬似コードはhere

Answer 1

を見つけることができる、つまり、与えられた点は、凸多角形を形成し、パーティションがあるとき最も不均衡な

円を描くと、角度が幾何学的に減少します。

Answer 2

最悪のケースの時間計算動作を生成できる点の集合を構築することは、あなたが研究している材料に与えられている特定の擬似コードに依存します。

Quickhullの最悪の場合の複雑性はO（N ）であり、平均的なケースのパフォーマンスがO（NlogN）あります。あなたが見てきたように、クイックハルは分裂征服戦略に従います。したがって、後者（すなわち、より良い）時間の複雑さを達成することは、問題を2つの同様のサイズの（理想的には等しい）副問題に分割することに依存する。分割ステップが平衡しておらず、2つのサブ問題の要素数が大きく異なる場合、アルゴリズムはN回繰り返さなければならない。換言すれば、各再帰的ステップにおいて、問題のサイズは、元の問題のサイズの数分の1に減少するのではなく、一定量だけ減少する。

ここで指定した擬似コードは、最低と最高のX座標（左端と右端の点）を持つ点を境界として2つの領域に分割します。理想的には、これは2つの等しく大きなセットにポイントを分割する必要があります。しかし、もしこのメソッドが入力として与えられた特定のポイントによって非効率にレンダリングされるなら、どうでしょうか？次に、各ステップで一定量のポイント、たとえばcを除外し、残りの半分にはまだN-cポイントが含まれます。したがって、問題はO（N）のステップを繰り返す必要があり、2次的な複雑さに終わることになります。

このような例の1つは、以下に示すように、ポイントを持つV字形を描くと思います。

(0, 5) 
(10, 5) 
(1, 4) 
(9, 4) 
(2, 3) 
(8, 3) 
(3, 2) 
(7, 2) 
(4, 1) 
(6, 1) 
(5, 0)