ホップクロフトの問題

点線入射に関するアルゴリズムの問題

計算幾何学において、ホップクロフトの問題は、ユークリッド平面上の点と直線の与えられた系について、少なくとも 1 つの点が少なくとも 1 つの直線上にあるかどうかをテストする問題です。より一般的には、点と直線の交差の数を求めることができます。この問題の両方のバージョンはの時間で解くことができます。ここでは点と直線の総数です。^{[1]この時間制限は、}セメレディ・トロッターの定理によって与えられた点と直線の交差の総数に対するの制限と一致します。^[2]ホップクロフトの問題は、1980 年代初頭にこの問題を提起したジョン・ホップクロフトにちなんで名付けられました。 ^[3]その計算複雑度は、3 次元ユークリッド最小全域木の問題など、計算幾何学における他のいくつかの問題の計算複雑度と密接に関連しています。^[1] $O(n^{4/3})$ $n$ $O(n^{4/3})$

アルゴリズム

この問題を解く一つの方法として、幾何学的な分割統治アルゴリズムを用いる。与えられた点と直線の系に対し、イプシロンネット理論を用いて、与えられたパラメータに対して平面を、直線の一部が交差し、点の一部を含む三角形のサブ問題に分割することができる。あるいは、同じ手法を双対直線と双対点の射影双対系に適用することで、入力直線の一部と点の一部を含むサブ問題を得ることができる。これを各方向に1回ずつ、に対して行うことで、問題は直接解くことができる一定サイズの部分問題に縮小される。この考え方（パラメータをより慎重に選ぶこと）により、の時間制限が導かれる。ここで、余分な対数係数は、このようにして生成されたサブ問題に点と直線を割り当てるオーバーヘッドから生じる。^[4] $r$ $O(r)$ $1/r^{2}$ $1/r$ $1/r$ $1/r^{2}$ $r=n^{1/3}$ $r$ $O(n^{4/3}\log^{1/3}n)$

同じ2段階の細分化プロセスにおいて、対数係数だけ小さいを選択することで、与えられた問題を、の時間での多重対数関数のサイズを持つ部分問題に縮小することができます。入力が一定サイズの部分問題に縮小されるまでこのプロセスを再帰的に繰り返すと、の形式の時間境界が得られます。ここでは反復対数を表します。^[5] $r$ $n$ $O(n^{4/3})$ $n^{4/3}2^{O(\log^{*}n)}$ $\log^{*}n$

2024 年の論文で、Chan と Zheng は、深さがであるホップクロフトの問題に対する代数決定木が存在することを示しました。^[1]これらは指数関数的なサイズであり効率的に構築できないため、ホップクロフトの問題を直接解決するために使用することはできませんが、分割統治法と組み合わせて使用できます。Jiří MatoušekによるDavid Eppsteinへの提案を受けて、^[5] Chan と Zheng は、再帰アルゴリズムの定数レベルの実行により、問題を、サイズが元の入力サイズの反復対数である多数のサブ問題に縮小するアルゴリズムについて説明します。これは、最適な決定木を総当たり探索で構築し、各サブ問題を解決するために使用するには十分に小さいです。結果は、合計時間であるホップクロフトの問題に対するアルゴリズムです。^[1] $O(n^{4/3})$ $O(n^{4/3})$

2024年のプレプリントにおいて、アンドレイエフス、ベロフス、ヴィフロフスは、ホップクロフト問題に対する量子アルゴリズムを発表しました。このアルゴリズムは時間で実行されますが、表記法によって対数係数が隠蔽されています。これは、古典アルゴリズムの既知の最良限界時間を大幅に下回っています。^[6] ${\tilde {O}}(n^{5/6})$ ${\tilde {O}}$

下限

ホップクロフトのアルゴリズムの自然な制限は点と直線の交差の数であり、これはセメレディ・トロッターの定理によって制限される可能性があります。^[2]これはまた、すべての点と直線の交差をリストするアルゴリズムの下限を提供しますが、交差があるかどうかを検出したり、交差を数えたりするためのアルゴリズムの下限を提供しません。 $\Theta (n^{4/3})$

ホップクロフトのアルゴリズムにおける分割統治アルゴリズムは、入力点と線が与えられた平面とその双対射影平面を単純に分割することによって機能します。ジェフ・エリクソンは、このように動作するアルゴリズムには必ず時間がかかるという下限を証明しました。^[3]しかし、代数的決定木に基づく手法はこのモデルに適合せず、エリクソンの下限は代数的決定木には適用されません。深さの問題に対する代数的決定木が存在する場合、それらを同様に使用してホップクロフトの問題をの時間で解くことができます。^[1] $\オメガ (n^{4/3})$ $o(n^{4/3})$ $o(n^{4/3})$

参考文献

^ abcde Chan, Timothy M. ; Zheng, Da Wei (2024)、「ホップクロフトの問題、対数^{シェービング}、2次元分数カスケーディング、および決定木」、ACM Transactions on Algorithms、20 (3): 24、doi :10.1145/3591357
^ ab Szemerédi, Endre ; Trotter, William T. (1983)、「離散幾何学における極限問題」、Combinatorica、3 ( 3– 4): 381– 392、doi :10.1007/BF02579194、MR 0729791
^ ab Erickson, J. (1996)、「ホップクロフトの問題に対する新しい下限値」、離散・計算幾何学、16 (4): 389– 418、doi :10.1007/BF02712875、MR 1414963
^ チャゼル、バーナード（1993）「分割統治のための超平面の切断」離散幾何学と計算幾何学、9（2）：145-158、doi：10.1007/BF02189314、MR 1194032
^ ab Matoušek, Jiří (1993)、「効率的な階層的カッティングによる範囲検索」、Discrete & Computational Geometry、10 (2): 157– 182、doi :10.1007/BF02573972、MR 1220545
^ アンドレエフス、ウラジミール;ベロフス、アレクサンドルス。 Vihrovs、Jevgēnijs (2024)、ホップクロフト問題の量子アルゴリズム、arXiv : 2405.01160

[chan-zheng-1] Chan, Timothy M. ; Zheng, Da Wei (2024)、「ホップクロフトの問題、対数^{シェービング}、2次元分数カスケーディング、および決定木」、ACM Transactions on Algorithms、20 (3): 24、doi :10.1145/3591357

[szemeredi-trotter-2] Szemerédi, Endre ; Trotter, William T. (1983)、「離散幾何学における極限問題」、Combinatorica、3 ( 3– 4): 381– 392、doi :10.1007/BF02579194、MR 0729791

[erickson-3] Erickson, J. (1996)、「ホップクロフトの問題に対する新しい下限値」、離散・計算幾何学、16 (4): 389– 418、doi :10.1007/BF02712875、MR 1414963

[chazelle-4] チャゼル、バーナード（1993）「分割統治のための超平面の切断」離散幾何学と計算幾何学、9（2）：145-158、doi：10.1007/BF02189314、MR 1194032

[matousek-5] Matoušek, Jiří (1993)、「効率的な階層的カッティングによる範囲検索」、Discrete & Computational Geometry、10 (2): 157– 182、doi :10.1007/BF02573972、MR 1220545

[anbevi-6] アンドレエフス、ウラジミール;ベロフス、アレクサンドルス。 Vihrovs、Jevgēnijs (2024)、ホップクロフト問題の量子アルゴリズム、arXiv : 2405.01160