Euclidean shortest path (original) (raw)
El problema del camino más corto de Euclides es un problema en geometría computacional: dado un conjunto de obstáculos poliédricos en un espacio Euclídeo, y dos puntos, encontrar el camino más corto entre los puntos que no se interseque con ninguno de los obstáculos.
| Property | Value |
|---|---|
| dbo:abstract | The Euclidean shortest path problem is a problem in computational geometry: given a set of polyhedral obstacles in a Euclidean space, and two points, find the shortest path between the points that does not intersect any of the obstacles. In two dimensions, the problem can be solved in polynomial time in a model of computation allowing addition and comparisons of real numbers, despite theoretical difficulties involving the numerical precision needed to perform such calculations. These algorithms are based on two different principles, either performing a shortest path algorithm such as Dijkstra's algorithm on a visibility graph derived from the obstacles or (in an approach called the continuous Dijkstra method) propagating a wavefront from one of the points until it meets the other. In three (and higher) dimensions the problem is NP-hard in the general case, but there exist efficient approximation algorithms that run in polynomial time based on the idea of finding a suitable sample of points on the obstacle edges and performing a visibility graph calculation using these sample points. There are many results on computing shortest paths which stays on a polyhedral surface. Given two points s and t, say on the surfaceof a convex polyhedron, the problem is to compute a shortest path that never leaves the surface and connects s with t. This is a generalization of the problem from 2-dimension but it is much easier than the 3-dimensional problem. Also, there are variations of this problem, where the obstacles are weighted, i.e., one can go through an obstacle, but it incursan extra cost to go through an obstacle. The standard problem is the special case where the obstacles have infinite weight. This istermed as the in the literature. (en) El problema del camino más corto de Euclides es un problema en geometría computacional: dado un conjunto de obstáculos poliédricos en un espacio Euclídeo, y dos puntos, encontrar el camino más corto entre los puntos que no se interseque con ninguno de los obstáculos. En dos dimensiones, el problema puede resolverse en tiempo polinómico en un modelo de computación que permita sumar y comparar números reales, a pesar de las dificultades teóricas que implica la precisión numérica necesaria para realizar dichos cálculos. Estos algoritmos se basan en dos principios diferentes, ya sea realizando un algoritmo que dé el camino más corto como el algoritmo de Dijkstra en un grafo de visibilidad derivado de los obstáculos o propagando un frente de onda desde uno de los puntos hasta que se encuentra con el otro. En tres dimensiones (y mayores) el problema es NP-Hard en el caso general, pero existen algoritmos de aproximación eficientes que se ejecutan en tiempo polinomial basados en la idea de encontrar una muestra adecuada de puntos en los bordes de los obstáculos y realizar un cálculo gráfico de visibilidad utilizando estos puntos de muestra. Hay muchos resultados en el cálculo de las trayectorias más cortas que permanecen en una superficie poliédrica. Dados dos puntos s y t, digamos en la superficie de un poliedro convexo, el problema es calcular el camino más corto que nunca salga de la superficie y conecte s con t. Esta es una generalización del problema de 2 dimensiones pero es mucho más fácil que el problema de 3 dimensiones. Además, hay variaciones de este problema, donde los obstáculos son pesados, es decir, uno puede pasar a través de un obstáculo, pero esto tiene un costo extra para pasar a través ese obstáculo. El problema estándar es el caso especial en el que los obstáculos tienen un peso infinito. Esto se denomina el problema de la región pesada. (es) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Euclidean_Shortest_Path_KernelCAD_Screenshot.jpg?width=300 |
| dbo:wikiPageExternalLink | http://cgm.cs.mcgill.ca/~godfried/publications/geodesic.pdf http://link.springer.de/link/service/journals/00453/contents/01/0027/ http://www.dynoinsight.com/ESP.htm http://portal.acm.org/citation.cfm%3Fid=314500.314560 |
| dbo:wikiPageID | 10976022 (xsd:integer) |
| dbo:wikiPageLength | 6817 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123170007 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Polyhedron dbr:NP-hard dbr:SIAM_Journal_on_Computing dbc:Geometric_algorithms dbr:Shortest_path_problem dbr:Computational_geometry dbr:File:Euclidean_Shortest_Path_KernelCAD_Screenshot.jpg dbc:Computational_geometry dbr:Euclidean_space dbr:Discrete_&_Computational_Geometry dbr:Journal_of_the_ACM dbr:Precision_(computer_science) dbr:Digital_Geometric_Kernel dbr:Dijkstra's_algorithm dbr:Convex_polyhedron dbr:Polynomial_time dbr:Visibility_graph dbr:Springer-Verlag dbr:Weighted_region_problem |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Combin-stub dbt:Geometry-stub dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Geometric_algorithms dbc:Computational_geometry |
| gold:hypernym | dbr:Problem |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGeometricAlgorithms yago:YagoPermanentlyLocatedEntity dbo:Disease yago:Rule105846932 |
| rdfs:comment | El problema del camino más corto de Euclides es un problema en geometría computacional: dado un conjunto de obstáculos poliédricos en un espacio Euclídeo, y dos puntos, encontrar el camino más corto entre los puntos que no se interseque con ninguno de los obstáculos. (es) The Euclidean shortest path problem is a problem in computational geometry: given a set of polyhedral obstacles in a Euclidean space, and two points, find the shortest path between the points that does not intersect any of the obstacles. In three (and higher) dimensions the problem is NP-hard in the general case, but there exist efficient approximation algorithms that run in polynomial time based on the idea of finding a suitable sample of points on the obstacle edges and performing a visibility graph calculation using these sample points. (en) |
| rdfs:label | Problema del camino más corto de Euclides (es) Euclidean shortest path (en) |
| owl:sameAs | freebase:Euclidean shortest path yago-res:Euclidean shortest path wikidata:Euclidean shortest path dbpedia-es:Euclidean shortest path https://global.dbpedia.org/id/4jX8e |
| prov:wasDerivedFrom | wikipedia-en:Euclidean_shortest_path?oldid=1123170007&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Euclidean_Shortest_Path_KernelCAD_Screenshot.jpg |
| foaf:isPrimaryTopicOf | wikipedia-en:Euclidean_shortest_path |
| is dbo:wikiPageRedirects of | dbr:Euclidean_shortest_path_problem |
| is dbo:wikiPageWikiLink of | dbr:Euclidean_shortest_path_problem dbr:Infinite-dimensional_optimization dbr:List_of_geometry_topics dbr:Shakey_the_robot dbr:Shortest_path_problem dbr:Computational_geometry dbr:Bitangent dbr:Digital_Geometric_Kernel dbr:Dijkstra's_algorithm dbr:Visibility_graph dbr:Sum_of_radicals |
| is foaf:primaryTopic of | wikipedia-en:Euclidean_shortest_path |
