ユークリッド最短経路

ユークリッド最短経路問題は、計算幾何学の問題です。ユークリッド空間内の多面体障害物の集合と 2 つの点が与えられたときに、どの障害物とも交差しない点間の最短経路を見つけます。

2 次元では、実数の加算と比較が可能な計算モデルで多項式時間で問題を解くことができますが、このような計算を実行するために必要な数値精度に関する理論的な困難さはあります。これらのアルゴリズムは、障害物から導出された可視性グラフでダイクストラのアルゴリズムなどの最短経路アルゴリズムを実行するか、(連続ダイクストラ法と呼ばれるアプローチで) 1 つのポイントから他のポイントに出会うまで波面を伝播するかのいずれかの異なる原理に基づいています。

3次元（およびそれ以上）では、一般にこの問題はNP困難であるが^[1]、障害物のエッジ上の適切なサンプル点を見つけ、これらのサンプル点を使用して可視性グラフの計算を実行するという考えに基づいて、多項式時間で実行される効率的な近似アルゴリズムが存在します。

多面体の表面上にとどまる最短経路の計算に関する結果は数多くあります。凸多面体の表面にある 2 つの点 s と t が与えられた場合、問題は、表面から出ることなく s と t を結ぶ最短経路を計算することです。これは 2 次元の問題の一般化ですが、3 次元の問題よりもはるかに簡単です。

この問題には、障害物に重みが付けられているバリエーションがあります。つまり、障害物を通過できますが、障害物を通過するには追加のコストがかかります。標準的な問題は、障害物の重みが無限大である特殊なケースです。これは、文献では 重み付き領域問題と呼ばれています。

• 最短経路問題、辺と頂点のグラフ
• グリッド空間における任意の角度の経路計画

• Aleksandrov, Lyudmil; Maheshwari, Anil; Sack, Joerg (2005)、「重み付き多面体表面における近似最短経路の決定」、Journal of the ACM、52 : 25–53、doi :10.1145/1044731.1044733、S2CID  697658。
• Chiang, Yi-Jen、Mitchell, Joseph SB (1999)、「平面における 2 点ユークリッド最短経路クエリ」、Proc. 10th ACM-SIAM Symposium on Discrete Algorithms (SODA 1999)、Association for Computing Machinery、pp. 215–224、ISBN 9780898714340。
• Choi, Joonsoo; Sellen, Jürgen; Yap, Chee-Keng (1994)、「3 次元空間における近似ユークリッド最短経路」、Proc. 10th ACM Symposium on Computational Geometry、pp. 41–48、doi :10.1145/177424.177501、ISBN 0-89791-648-4、S2CID  69747。
• Hershberger, John; Suri, Subhash (1999)、「平面におけるユークリッド最短経路の最適アルゴリズム」、SIAM Journal on Computing、28 (6): 2215–2256、CiteSeerX  10.1.1.47.2037、doi :10.1137/S0097539795289604。
• Kapoor, S.; Maheshwari, SN (1988)、「多角形障害物のあるユークリッド最短経路および可視性問題に対する効率的なアルゴリズム」、Proc. 4th ACM Symposium on Computational Geometry、pp. 172–182、doi :10.1145/73393.73411、ISBN 0-89791-270-5、S2CID  9599057。
• Kapoor, S.; Maheshwari, SN; Mitchell, Joseph SB (1997)、「平面上の多角形障害物間のユークリッド最短経路の効率的なアルゴリズム」、Discrete & Computational Geometry、18 (4): 377–383、doi : 10.1007/PL00009323。
• Lanthier, Mark; Maheshwari, Anil; Sack, Jörg-Rüdiger (2001)、「重み付き多面体表面上の最短経路の近似」、Algorithmica、pp. 527–562。
• Lee, DT ; Preparata, FP (1984)、「直線障壁がある場合のユークリッド最短経路」、Networks、14 (3): 393–410、doi :10.1002/net.3230140304。
• リー、ファジェ。 Klette、Reinhard (2011)、ユークリッド最短経路: 正確または近似アルゴリズム、Springer-Verlag、doi :10.1007/978-1-4471-2256-2、ISBN 978-1-4471-2255-5。
• サミュエル、デイビッド;トゥーサン、ゴッドフリード T. (1990)、「単純な多角形の外部測地線直径の計算」、コンピューティング、44 (1): 1–19、doi :10.1007/BF02247961、S2CID  31450333。
• トゥーサン、ゴッドフリード T. (1989)、「単純な多角形内の測地線特性の計算」(PDF)、Revue d'Intelligence Artificielle、3 (2): 9–42。

• デジタル幾何カーネルソフトウェアにおけるユークリッド最短経路アルゴリズムの実装