ホップクロフトの問題

計算幾何学 において、ホップクロフトの問題とは、ユークリッド平面上の点と直線の系が与えられたとき、少なくとも1つの点が少なくとも1つの直線上にあるかどうかを判定する問題である。より一般的には、点と直線の交わりの数を求める問題とも言える。どちらの問題も時間で解くことができる。${\displaystyle O(n^{4/3})}$、 どこ${\displaystyle n}$は点と線の総数です。^{[ 1 ]}この時間制限は、${\displaystyle O(n^{4/3})}$点と直線の交点の総数は、Szemerédi–Trotter の定理によって与えられます。^{[ 2 ]} Hopcroft の問題は、1980 年代初頭にこの問題を提起したJohn Hopcroftにちなんで名付けられました。 ^{[ 3 ]}その計算複雑性は、3 次元ユークリッド最小全域木の問題など、計算幾何学における他のいくつかの問題の複雑性と密接に関連しています。^{[ 1 ]}

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

同じ2段階の分割プロセスで、${\displaystyle r}$対数係数で小さくなると、与えられた問題を、サイズが多対数関数である部分問題に縮小することができます。${\displaystyle n}$やがて${\displaystyle O(n^{4/3})}$入力が一定サイズのサブ問題に縮小されるまでこのプロセスを再帰的に繰り返すと、次の形式の時間制限が得られます。${\displaystyle n^{4/3}2^{O(\log ^{*}n)}}$。 ここ${\displaystyle \log ^{*}n}$は反復対数を表します。^{[ 5 ]}

2024年の論文で、ChanとZhengは、深さが次の代数的決定木がホップクロフト問題に対して存在することを示しました。${\displaystyle O(n^{4/3})}$[ ^{1 ]}これらは指数関数的なサイズを持ち、効率的に構築できないため、ホップクロフト問題を直接解決するために使用することはできません。しかし、分割統治法と組み合わせて使用​​することは可能です。イジー・マトウシェクがデイビッド・エプスタインに帰属する提案に基づき^、 [ 5 ]チャン^{とジェンは}、再帰アルゴリズムを一定回数実行し、問題を元の入力サイズの反復対数であるサイズの多数のサブ問題に縮小するアルゴリズムを記述しています。これは、総当たり探索によって最適な決定木を構築し、各サブ問題を解くために使用できるほど小さいサイズです。結果として、ホップクロフト問題に対するアルゴリズムが得られ、その合計時間は${\displaystyle O(n^{4/3})}$[ ^{1 ]​}

2024年のプレプリントで、Andrejevs、Belovs、およびVihrovsは、ホップクロフト問題に対する量子アルゴリズムを発表した。このアルゴリズムは、$\displaystyle {\tilde {O}}(n^{5/6})}$、$\displaystyle {\tilde {O}}}$表記法は対数因子を隠蔽します。これは古典的なアルゴリズムの既知の最良の時間制限を大幅に下回ります。^{[ 6 ]}

ホップクロフトのアルゴリズムの自然な制限は、点と線の交点の数であり、$\displaystyle \Theta (n^{4/3})$Szemerédi–Trotterの定理により。^{[ 2 ]}これは、すべての点と線の関連性を列挙するアルゴリズムの下限も提供しますが、関連性があるかどうかを検出したり、関連性を数えたりするアルゴリズムの下限は提供しません。

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