- Euclidean shortest path
This problem is studied in
computational geometry : given a set of polyhedral obstacles in a Euclidean space, having a total of n vertices;design algorithms for efficient (exact or approximate) calculation of a shortest, obstacle-avoiding path connecting any two query points.In 2D, and among polygonal obstacles, efficient solutions exist to most (all?) shortest path problems. However, in 3D and among polyhedral obstacles, even the basic problem of computing the shortest path between two points is NP-hard.
External links
oftware
* [http://www.VisiLibity.org VisiLibity: A free open source C++ library of floating-point visibility algorithms and supporting data types. This software uses the visibility graph method for calculating Euclidean shortest paths through polygonal environments with polygonal holes. A Matlab interface is also included.]
References
* [http://www.ams.stonybrook.edu/~jsbm/publications.html J.S.B. Mitchell,"Geometric Shortest Paths and Network Optimization"Draft of a survey chapter for the Handbook of Computational Geometry, Elsevier Science, (J.-R. Sack and J. Urrutia, eds.), 2000. (Now appears as Chapter 15, pages 633--701.) ]
Wikimedia Foundation. 2010.