チャンのアルゴリズム

計算幾何学において、ティモシー・M・チャンにちなんで名付けられたチャンのアルゴリズム[ ^1]は、2次元または3次元空間の点の集合の凸包を計算するための最適な出力依存アルゴリズムです。このアルゴリズムには時間がかかります。ここで、は出力（凸包）の頂点の数です。平面の場合、アルゴリズムは最適な時間を得るために、アルゴリズム（たとえばグラハムスキャン）とジャービスマーチ（ ）を組み合わせます。チャンのアルゴリズムは、カークパトリック-ザイデルアルゴリズムよりもはるかに単純で、3次元空間に自然に拡張できることで注目に値します。このパラダイム^[2]は、フランク・ニールセンが博士論文で独自に開発しました。^[3]${\displaystyle P}$${\displaystyle n}$${\displaystyle O(n\log h)}$${\displaystyle h}$${\displaystyle O(n\log n)}$${\displaystyle O(nh)}$${\displaystyle O(n\log h)}$

アルゴリズムの 1 回のパスでは、0 から(集合 の点の数)までのパラメータが必要です。理想的には、出力凸包の頂点の数 は、開始時には不明です。 の値を増加させながら複数のパスが実行され、 になると終了します(パラメータ の選択については以下を参照)。 ${\displaystyle m}$${\displaystyle n}$${\displaystyle P}$${\displaystyle m=h}$${\displaystyle h}$${\displaystyle m}$${\displaystyle m\geq h}$${\displaystyle m}$

アルゴリズムは、点の集合をそれぞれ最大で 個の点を持つサブセットに任意に分割することから始まります。 に注意してください。 ${\displaystyle P}$${\displaystyle K=\lceil n/m\rceil }$${\displaystyle (Q_{k})_{k=1,2,...K}}$${\displaystyle m}$${\displaystyle K=O(n/m)}$

各サブセット について、アルゴリズム (たとえば、グラハムスキャン)を使用して凸包 を計算します。ここで、 はサブセット内の点の数です。それぞれ の点のサブセットがあるため、このフェーズには時間がかかります。 ${\displaystyle Q_{k}}$${\displaystyle C_{k}}$${\displaystyle O(p\log p)}$${\displaystyle p}$${\displaystyle K}$${\displaystyle O(m)}$${\displaystyle K\cdot O(m\log m)=O(n\log m)}$

第 2 段階では、事前に計算された (ミニ) 凸包 を利用して、ジャービスの行進が実行されます。このジャービスの行進アルゴリズムの各ステップでは、凸包 内に点があり(最初は 内の最低の y 座標を持つ点である可能性があり、これは の凸包内にあることが保証されています)、の他のすべての点が線の右側にあるような点を見つける必要があります^{[明確化が必要]}。ここで、 という表記は、次の点、つまり がおよびの関数として決定されることを単に意味しています。集合 の凸包 は既知であり、最大 個の点 (時計回りまたは反時計回りの順序でリストされている) を含み、これにより、バイナリ検索によって 1 時間でを計算することができます^[方法] 。したがって、すべてのサブセットに対するの計算は1 時間で実行できます。次に、ジャービスの行進で通常使用されるのと同じ手法を使用してを決定できますが、集合 全体ではなく、点 (つまり、ミニ凸包内の点)のみを考慮します。これらの点の場合、ジャービスの行進の 1 回の反復は であり、これはすべてのサブセットの計算と比較すると無視できます。ジャービスの行進は、プロセスが 回繰り返されたときに完了します(ジャービスの行進の仕組みでは、の凸包内の点の数である最も外側のループを最大 回繰り返した後、凸包が見つかる必要があるため)。したがって、2 番目のフェーズには 時間がかかり、が に近い場合は の時間と等しくなります (この場合に当てはまるように を選択する戦略の説明を以下で参照してください)。${\displaystyle (C_{k})_{k=1,2,...K}}$${\displaystyle p_{i}}$${\displaystyle p_{i}}$${\displaystyle P}$${\displaystyle P}$${\displaystyle p_{i+1}=f(p_{i},P)}$${\displaystyle P}$${\displaystyle p_{i}p_{i+1}}$${\displaystyle p_{i+1}=f(p_{i},P)}$${\displaystyle p_{i+1}}$${\displaystyle p_{i}}$${\displaystyle P}$${\displaystyle Q_{k}}$${\displaystyle C_{k}}$${\displaystyle m}$${\displaystyle f(p_{i},Q_{k})}$${\displaystyle O(\log m)}$${\displaystyle f(p_{i},Q_{k})}$${\displaystyle K}$${\displaystyle O(K\log m)}$${\displaystyle f(p_{i},P)}$${\displaystyle (f(p_{i},Q_{k}))_{1\leq k\leq K}}$${\displaystyle P}$${\displaystyle O(K)}$${\displaystyle O(h)}$${\displaystyle h}$${\displaystyle h}$${\displaystyle P}$${\displaystyle O(Kh\log m)}$${\displaystyle O(n\log h)}$${\displaystyle m}$${\displaystyle h}$${\displaystyle m}$

上記の 2 つのフェーズを実行すると、点の凸包が時間内に計算されます。 ${\displaystyle n}$${\displaystyle O(n\log h)}$

に任意の値を選択した場合、 が発生する可能性があります。その場合、第 2 フェーズのステップの後に、ジャービスの行進を最後まで実行すると時間がかかりすぎるため、ジャービスの行進を中断します。その時点で、時間が経過し、凸包は計算されません。 ${\displaystyle m}$${\displaystyle m<h}$${\displaystyle m}$${\displaystyle O(n\log m)}$

この考え方は、 の値を増加させながらアルゴリズムのパスを複数回実行し、各パスが時間内に（成功または失敗に関わらず）終了するというものです。のパス間の増加が遅すぎると、反復回数が大きくなる可能性があります。一方、 の上昇が速すぎると、アルゴリズムが正常に終了する最初の回数が よりもはるかに大きくなり、複雑度 が生じる可能性があります。 ${\displaystyle m}$${\displaystyle O(n\log m)}$${\displaystyle m}$${\displaystyle m}$${\displaystyle h}$${\displaystyle O(n\log m)>O(n\log h)}$

1つの可能な戦略は、各反復で の値を2乗し、最大値（シングルトンセットの分割に対応）まで増やすことです。^[4]反復で 2の値から始めて、が選択されます。その場合、アルゴリズムは ${\displaystyle m}$${\displaystyle n}$${\displaystyle t}$${\displaystyle m=\min \left(n,2^{2^{t}}\right)}$${\displaystyle O(\log \log h)}$

${\displaystyle m=2^{2^{t}}\geq h\iff \log \left(2^{2^{t}}\right)\geq \log h\iff 2^{t}\geq \log h\iff \log {2^{t}}\geq \log {\log h}\iff t\geq \log {\log h},}$

対数を底としてとると、アルゴリズムの実行時間の合計は ${\displaystyle 2}$

${\displaystyle \sum _{t=0}^{\lceil \log \log h\rceil }O\left(n\log \left(2^{2^{t}}\right)\right)=O(n)\sum _{t=0}^{\lceil \log \log h\rceil }2^{t}=O\left(n\cdot 2^{1+\lceil \log \log h\rceil }\right)=O(n\log h).}$

この構築を3次元の場合に一般化するには、グラハムスキャンの代わりにプレパラタとホンによる3次元凸包を計算するアルゴリズムを使用し、ジャービスの行進の3次元バージョンを使用する必要があります。時間計算量はそのままです。^[1]${\displaystyle O(n\log n)}$${\displaystyle O(n\log h)}$

次の擬似コードでは、括弧内と斜体で書かれたテキストはコメントです。次の擬似コードを完全に理解するには、読者が点の集合 の 凸包 を計算するGraham スキャン アルゴリズムとJarvis Marchアルゴリズムについてすでに理解していることが推奨されます。 ${\displaystyle C}$${\displaystyle P}$

入力:ポイントで設定します。${\displaystyle P}$${\displaystyle n}$

出力:点を設定した、 の凸包。${\displaystyle C}$${\displaystyle h}$${\displaystyle P}$

(が 内にあることが保証される点を選択します。たとえば、y 座標が最も低い点などです。)${\displaystyle P}$${\displaystyle C}$

(この操作には時間がかかります。たとえば、 を単純に反復処理することができます。)${\displaystyle {\mathcal {O}}(n)}$${\displaystyle P}$

${\displaystyle p_{1}:=PICK\_START(P)}$

（このChanのアルゴリズムのJarvis Marchの部分で使用されている。${\displaystyle p_{0}}$

の凸包の2 番目の点 を計算するために、 を使用します。${\displaystyle p_{2}}$${\displaystyle P}$

(注:は の点ではありません。)${\displaystyle p_{0}}$${\displaystyle P}$

(詳細については、Chan のアルゴリズムの対応する部分の近くにあるコメントを参照してください。)

${\displaystyle p_{0}:=(-\infty ,0)}$

(注:の最終的な凸包内の点の数は不明です。)${\displaystyle h}$${\displaystyle P}$

(これらはの推定値である の値を発見するために必要な反復です。)${\displaystyle m}$${\displaystyle h}$

(の凸包を見つけるには、この Chan のアルゴリズムに必要です。)${\displaystyle h\leq m}$${\displaystyle P}$

（より具体的には、不要な反復をあまり実行しないようにするために、${\displaystyle h\leq m\leq h^{2}}$

そして、この Chan のアルゴリズムの時間計算量は となる。${\displaystyle {\mathcal {O}}(n\log h)}$

(この記事で上で説明したように、を見つけるために最大で 回の反復が必要となる戦略が使用されます。)${\displaystyle \log \log n}$${\displaystyle m}$

(注意: 最終値は と等しくならない場合もありますが、 より小さくなったりより大きくなったりすることはありません。)${\displaystyle m}$${\displaystyle h}$${\displaystyle h}$${\displaystyle h^{2}}$

（それにもかかわらず、このチャンのアルゴリズムは、最も外側のループの反復が実行されると停止します。${\displaystyle h}$

つまり、 の場合でも、最も外側のループの反復は実行されません。${\displaystyle m\neq h}$${\displaystyle m}$

(詳細については、このアルゴリズムの以下の Jarvis 行進の部分を参照してください。の場合は が返されます。)${\displaystyle C}$${\displaystyle p_{i+1}==p_{1}}$

行うために${\displaystyle 1\leq t\leq \log \log n}$

(現在の反復のパラメータを設定します。この記事で上で説明したように、「二乗スキーム」が使用されます。${\displaystyle m}$

他にも方式はあります。たとえば、「倍増方式」では、に対して となります。${\displaystyle m=2^{t}}$${\displaystyle t=1,\dots ,\left\lceil \log h\right\rceil }$

ただし、「倍増方式」を使用すると、この Chan のアルゴリズムの結果として生じる時間計算量は次のようになります。${\displaystyle {\mathcal {O}}(n\log ^{2}h)}$

${\displaystyle m:=2^{2^{t}}}$

( の凸包の点が見つかったら、それを保存するために空のリスト (または配列) を初期化します。)${\displaystyle P}$

${\displaystyle C:=()}$

${\displaystyle ADD(C,p_{1})}$

(点の集合を、それぞれおよそ要素のサブセットに任意に分割します。)${\displaystyle P}$${\displaystyle K=\left\lceil {\frac {n}{m}}\right\rceil }$${\displaystyle m}$

${\displaystyle Q_{1},Q_{2},\dots,Q_{K}:=SPLIT(P,m)}$

(点のすべての部分集合の凸包を計算します。)${\displaystyle K}$${\displaystyle Q_{1},Q_{2},\dots ,Q_{K}}$

（時間がかかります。）${\displaystyle {\mathcal {O}}(Km\log m)={\mathcal {O}}(n\log m)}$

の場合、時間計算量は です。${\displaystyle m\leq h^{2}}$${\displaystyle {\mathcal {O}}(n\log h^{2})={\mathcal {O}}(n\log h)}$

行うために${\displaystyle 1\leq k\leq K}$

(サブセットの凸包をグラハムスキャンを使用して計算しますが、時間がかかります。)${\displaystyle k}$${\displaystyle Q_{k}}$${\displaystyle {\mathcal {O}}(m\log m)}$

( は点の部分集合の凸包です。)${\displaystyle C_{k}}$${\displaystyle Q_{k}}$

${\displaystyle C_{k}:=GRAHAM\_SCAN(Q_{k})}$

(この時点で、それぞれの点のサブセットの凸包が計算されています。)${\displaystyle C_{1},C_{2},\dots ,C_{K}}$${\displaystyle Q_{1},Q_{2},\dots ,Q_{K}}$

(ここで、Jarvis Marchアルゴリズムの修正版を使用して、 の凸包を計算します。)${\displaystyle P}$

(ジャービス行進は時間で実行されます。ここで、は入力ポイントの数、は凸包内のポイントの数です。)${\displaystyle {\mathcal {O}}(nh)}$${\displaystyle n}$${\displaystyle h}$

(ジャービス行進は出力に敏感なアルゴリズムであるため、その実行時間は凸包のサイズに依存します。)${\displaystyle h}$

(実際には、Jarvis March が最も外側のループの反復を実行することを意味します。${\displaystyle h}$

これらの各反復では、最も内側のループの最大反復が実行されます。${\displaystyle n}$

( が必要なので、次の外側のループで 回以上の反復を実行したくありません。)${\displaystyle h\leq m\leq h^{2}}$${\displaystyle m}$

(電流が より小さい場合、つまり の場合、 の凸包は見つかりません。)${\displaystyle m}$${\displaystyle h}$${\displaystyle m<h}$${\displaystyle P}$

(この Jarvis March の修正バージョンでは、最も内側のループ内で時間のかかる操作を実行します。${\displaystyle {\mathcal {O}}(\log m)}$

したがって、この修正版の合計時間計算量は

${\displaystyle {\mathcal {O}}(mK\log m)={\mathcal {O}}(m\left\lceil {\frac {n}{m}}\right\rceil \log m)={\mathcal {O}}(n\log m)={\mathcal {O}}(n\log 2^{2^{t}})={\mathcal {O}}(n2^{t}).}$

の場合、時間計算量は です。${\displaystyle m\leq h^{2}}$${\displaystyle {\mathcal {O}}(n\log h^{2})={\mathcal {O}}(n\log h)}$

行うために${\displaystyle 1\leq i\leq m}$

(注: ここで、 の凸包内の点はすでに分かっています。つまり、 です。)${\displaystyle P}$${\displaystyle p_{1}}$

(この内部のforループでは、、の凸包上にある可能性のある次の点が計算されます。)${\displaystyle K}$${\displaystyle P}$${\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}$

(これらの可能性のある次のポイントはそれぞれ異なるものです:${\displaystyle K}$${\displaystyle C_{k}}$

つまり、は の凸包上の次の点となり得る点であり、 は の凸包の一部です。${\displaystyle q_{i,k}}$${\displaystyle P}$${\displaystyle C_{k}}$

(注:は に依存します。つまり、各反復 に対して、の凸包上にある可能性のある次の点が存在します。)${\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}$${\displaystyle i}$${\displaystyle i}$${\displaystyle K}$${\displaystyle P}$

(注: 各反復において、 内の点のうち 1 つだけがの凸包に追加されます。)${\displaystyle i}$${\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}$${\displaystyle P}$

行うために${\displaystyle 1\leq k\leq K}$

（角度が最大になる点を見つける^{[なぜ？ ]}、${\displaystyle JARVIS\_BINARY\_SEARCH}$${\displaystyle d\in C_{k}}$${\displaystyle \measuredangle p_{i-1}p_{i}d}$

ここで、 はベクトルと の間の角度です。これはに格納されます。${\displaystyle \measuredangle p_{i-1}p_{i}d}$${\displaystyle {\overrightarrow {p_{i}p_{i-1}}}}$${\displaystyle {\overrightarrow {p_{i}d}}}$${\displaystyle d}$${\displaystyle q_{i,k}}$

（角度を直接計算する必要はありません。方向テストを使用できます^{[どのように？ ]}。）

（時間内に実行できます^か？）${\displaystyle JARVIS\_BINARY\_SEARCH}$${\displaystyle {\mathcal {O}}(\log m)}$

(注: 反復 では、は既知であり、 は の凸包内の点です。${\displaystyle i=1}$${\displaystyle p_{i-1}=p_{0}=(-\infty ,0)}$${\displaystyle p_{1}}$${\displaystyle P}$

この場合は、y 座標が最も低い点になります。${\displaystyle P}$

${\displaystyle q_{i,k}:=JARVIS\_BINARY\_SEARCH(p_{i-1},p_{i},C_{k})}$

（角度^{[なぜ？ ]}を最大化する点をの凸包上の次の点として選択します。）${\displaystyle z\in \{q_{i,1},q_{i,2},\dots ,q_{i,K}\}}$${\displaystyle \measuredangle p_{i-1}p_{i}z}$ ${\displaystyle P}$

${\displaystyle p_{i+1}:=JARVIS\_NEXT\_CH\_POINT(p_{i-1},p_{i},(q_{i,1},q_{i,2},\dots ,q_{i,K}))}$

(ジャービス行進は、凸包上の次の選択された点 が初期点 になったときに終了します。)${\displaystyle p_{i+1}}$${\displaystyle p_{1}}$

もし ${\displaystyle p_{i+1}==p_{1}}$

(点を含む凸包を返します。)${\displaystyle P}$${\displaystyle i=h}$

(注: もちろん、と等しい を返す必要はありません。)${\displaystyle p_{i+1}}$${\displaystyle p_{1}}$

戻る ${\displaystyle C:=(p_{1},p_{2},\dots ,p_{i})}$

それ以外

${\displaystyle ADD(C,p_{i+1})}$

(反復後に となる点が見つからない場合はとなります。)${\displaystyle m}$${\displaystyle p_{i+1}}$${\displaystyle p_{i+1}==p_{1}}$${\displaystyle m<h}$

( の値をもっと高くしてやり直す必要があります。)${\displaystyle m}$

Chan の論文には、アルゴリズムの実際のパフォーマンスを向上させる可能性のあるいくつかの提案が含まれています。たとえば、

• サブセットの凸包を計算するときに、凸包に含まれないポイントを後続の実行の考慮から除外します。
• より大きな点集合の凸包は、最初から再計算するのではなく、以前に計算した凸包をマージすることによって取得できます。
• 上記の考え方では、アルゴリズムの主なコストは前処理、つまりグループの凸包の計算にあります。このコストを削減するには、前回の反復から計算された包を再利用し、グループ サイズが増加するにつれてそれらをマージすることを検討します。

Chan の論文には、彼の手法を使用して既知のアルゴリズムを最適な出力に敏感にすることができる他のいくつかの問題が含まれています。たとえば、

• 交点によって形成される無限台形の下限として定義される線分セットの下側エンベロープ を計算します。${\displaystyle L(S)}$${\displaystyle S}$${\displaystyle n}$
• ハーシュバーガー^[5]は、 まで高速化できるアルゴリズムを提示した。ここでhはエンベロープ内の辺の数である。${\displaystyle O(n\log n)}$${\displaystyle O(n\log h)}$

• 高次元の凸包に対する出力に敏感なアルゴリズムの構築。グループ化ポイントを使用し、効率的なデータ構造を使用することで、h が の多項式次数である場合に複雑さを実現できます。${\displaystyle O(n\log h)}$${\displaystyle n}$

• 凸包アルゴリズム