点集合の最大値

計算幾何学では、有限の点集合 $S$ 内の点 $p が$ 最大または非優越であるとは、 $S$ 内に、 $p$ の対応する座標よりも大きいか等しい座標を持つ他の点 $q$ が存在しない場合に言う。点集合 $Sの最大値は、$ $S$ のすべての最大点である。すべての最大点を見つける問題は、最大値の問題または最大集合問題と呼ばれることもあり、凸包問題および直交凸包問題の変形として研究されてきた。これは点の集合のパレート境界を見つけることに相当し、ハーバート・フリーマンによって、複数の通貨の異なる保有量を持つ個人の相対的な富の比較を含む応用に基づいて、変動通貨問題と呼ばれた。 ^[1]

2次元

2次元の点の場合、この問題は以下の手順を実行するアルゴリズムによって $O (n log n)の$ 時間で解くことができる: ^[1]^[2]

座標次元の1つ（たとえば $x$ 座標）で点を並べ替える
$各点について、 x$ 座標の降順で、その $y$ 座標が、以前に処理された点の $y$ 座標の最大値より大きいかどうかをテストします。(最初の点については、これは明らかに真です)。大きい場合は、その点を最大点の 1 つとして出力し、その $y$ 座標をこれまでに確認された最大のものとして記憶します。

点の座標が整数であると仮定すると、整数ソートアルゴリズムを使用してこれを高速化し、ソートアルゴリズムと同じ漸近的な実行時間を実現できます。^[3]

3次元

3次元の点の場合も、以下の手順を実行する2次元のアルゴリズムと同様のアルゴリズムを使用して、時間 $O (n log n)$ 内に最大点を見つけることができます。

座標次元の1つ（たとえば $x$ 座標）で点を並べ替える
$各点について、 x$ 座標の降順で、その点の $yz$ 平面への投影が、これまでに処理された点の集合の投影の集合の中で最大であるかどうかをテストします。最大である場合は、その点を最大点の 1 つとして出力し、その $y$ 座標をこれまでに確認された最大値として記憶します。

この方法は、静的な 3 次元点集合の最大点を計算する問題を、動的な 2 次元点集合の最大点を維持する問題に縮小します。2 次元の部分問題は、バランスのとれたバイナリ検索ツリーを使用して動的点集合の最大点集合を維持することにより、効率的に解決できます。このデータ構造を使用すると、新しい点が既存の点に支配されているかどうかをテストしたり、新しい点に支配されている以前は支配されていなかった点を見つけて削除したり、最大点集合に新しい点を追加したりすることができます。これらの処理は、点ごとに対数時間で実行できます。検索ツリー操作の回数はアルゴリズムの過程で線形であるため、合計時間は $O (n log n)$ です。^[1]^[2]

整数座標を持つ点の場合、アルゴリズムの最初の部分である点のソートは、整数ソートによって再び高速化できます。点が3つの次元すべてで個別にソートされている場合、座標の値の範囲は、任意の2つの座標の相対的な順序を変更せずに、また最大点のアイデンティティを変更することなく、 $1$ から $n$ の範囲に縮小できます。座標空間のこの縮小後、最大点の動的な2次元セットを維持する問題は、バランスのとれた2分探索木の代わりにファン・エムデ・ボアズ木を使用して解決できます。アルゴリズムに対するこれらの変更により、実行時間が $O (n log log n)$ に高速化されます。^[3]

高次元

任意の次元 $d$ では、すべての点のペアについて一方が他方を支配しているかどうかをテストし、支配されていない点を出力として報告することで、時間 $O (dn 2)$ で問題を解くことができます。ただし、 $d$ が 3 より大きい定数の場合、これは $O (n (log n) d - 3 log log n)$ に改善できます。^{[4]ランダムに生成された点集合の場合、問題を}線形時間で解くことができます。^[5]^[6]

参考文献

^ abc Preparata, Franco P. ; Shamos, Michael Ian (1985)、「セクション 4.1.3: 点集合の最大値の問題」、計算幾何学: 入門、コンピュータサイエンスのテキストとモノグラフ、Springer-Verlag、pp. 157–166、ISBN 0-387-96131-3。
^ ab Kung, HT ; Luccio, F.; Preparata, FP (1975)、「ベクトル集合の最大値の検出について」(PDF)、Journal of the ACM、22 (4): 469–476、doi :10.1145/321906.321910、MR 0381379、S2CID 2698043。
^ ab Karlsson, Rolf G.; Overmars, Mark H. (1988)、「グリッド上のスキャンラインアルゴリズム」、BIT Numerical Mathematics、28 (2): 227–241、doi :10.1007/BF01934088、hdl : 1874/16270、MR 0938390、S2CID 32964283。
^ Gabow, Harold N. ; Bentley, Jon Louis ; Tarjan, Robert E. (1984)、「Scaling and related Techniques for geometry issues」、Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (STOC '84)、ニューヨーク、ニューヨーク、米国: ACM、pp. 135–143、doi :10.1145/800057.808675、ISBN 0-89791-133-4、S2CID 17752833。
^ Bentley, Jon L. ; Clarkson, Kenneth L. ; Levine, David B. (1993)、「最大値と凸包を計算するための高速線形期待時間アルゴリズム」、Algorithmica、9 (2): 168–183、doi :10.1007/BF01188711、MR 1202289、S2CID 1874434。
^ Dai, HK; Zhang, XW (2004)、「最大値を計算するための改良線形期待時間アルゴリズム」、Farach-Colton, Martín (編)、LATIN 2004: 理論情報学、第 6 回ラテンアメリカシンポジウム、アルゼンチン、ブエノスアイレス、2004 年 4 月 5 ～ 8 日、議事録、コンピュータサイエンスの講義ノート、第 2976 巻、ベルリン: Springer-Verlag、pp. 181 ～ 192、doi :10.1007/978-3-540-24698-5_22、ISBN 978-3-540-21258-4、MR 2095193。

[ps-1] Preparata, Franco P. ; Shamos, Michael Ian (1985)、「セクション 4.1.3: 点集合の最大値の問題」、計算幾何学: 入門、コンピュータサイエンスのテキストとモノグラフ、Springer-Verlag、pp. 157–166、ISBN 0-387-96131-3。

[klp-2] Kung, HT ; Luccio, F.; Preparata, FP (1975)、「ベクトル集合の最大値の検出について」(PDF)、Journal of the ACM、22 (4): 469–476、doi :10.1145/321906.321910、MR 0381379、S2CID 2698043。

[ko-3] Karlsson, Rolf G.; Overmars, Mark H. (1988)、「グリッド上のスキャンラインアルゴリズム」、BIT Numerical Mathematics、28 (2): 227–241、doi :10.1007/BF01934088、hdl : 1874/16270、MR 0938390、S2CID 32964283。

[4] Gabow, Harold N. ; Bentley, Jon Louis ; Tarjan, Robert E. (1984)、「Scaling and related Techniques for geometry issues」、Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (STOC '84)、ニューヨーク、ニューヨーク、米国: ACM、pp. 135–143、doi :10.1145/800057.808675、ISBN 0-89791-133-4、S2CID 17752833。

[5] Bentley, Jon L. ; Clarkson, Kenneth L. ; Levine, David B. (1993)、「最大値と凸包を計算するための高速線形期待時間アルゴリズム」、Algorithmica、9 (2): 168–183、doi :10.1007/BF01188711、MR 1202289、S2CID 1874434。

[6] Dai, HK; Zhang, XW (2004)、「最大値を計算するための改良線形期待時間アルゴリズム」、Farach-Colton, Martín (編)、LATIN 2004: 理論情報学、第 6 回ラテンアメリカシンポジウム、アルゼンチン、ブエノスアイレス、2004 年 4 月 5 ～ 8 日、議事録、コンピュータサイエンスの講義ノート、第 2976 巻、ベルリン: Springer-Verlag、pp. 181 ～ 192、doi :10.1007/978-3-540-24698-5_22、ISBN 978-3-540-21258-4、MR 2095193。