Euclidean shortest path

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.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Shortest path problem — A graph with 6 vertices and 7 edges In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. An example is… …   Wikipedia

  • Dijkstra's algorithm — Not to be confused with Dykstra s projection algorithm. Dijkstra s algorithm Dijkstra s algorithm runtime Class Search algorithm Data structure Graph Worst case performance …   Wikipedia

  • List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

  • Computational geometry — is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to… …   Wikipedia

  • Travelling salesman problem — The travelling salesman problem (TSP) is an NP hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest… …   Wikipedia

  • Distance — This article is about distance in the mathematical or physical sense. For other senses of the term, see distance (disambiguation). Proximity redirects here. For the 2001 film, see Proximity (film). Distance (or farness) is a numerical description …   Wikipedia

  • geometry — /jee om i tree/, n. 1. the branch of mathematics that deals with the deduction of the properties, measurement, and relationships of points, lines, angles, and figures in space from their defining conditions by means of certain assumed properties… …   Universalium

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”