Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Euclidean_shortest_path> ?p ?o }
Showing triples 1 to 54 of
54
with 100 triples per page.
- Euclidean_shortest_path 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 weighted region problem in the literature.".
- Euclidean_shortest_path thumbnail Euclidean_Shortest_Path_KernelCAD_Screenshot.jpg?width=300.
- Euclidean_shortest_path wikiPageExternalLink geodesic.pdf.
- Euclidean_shortest_path wikiPageExternalLink citation.cfm?id=314500.314560.
- Euclidean_shortest_path wikiPageExternalLink 1044731.1044733.
- Euclidean_shortest_path wikiPageExternalLink 0027.
- Euclidean_shortest_path wikiPageExternalLink ESP.htm.
- Euclidean_shortest_path wikiPageID "10976022".
- Euclidean_shortest_path wikiPageLength "6293".
- Euclidean_shortest_path wikiPageOutDegree "22".
- Euclidean_shortest_path wikiPageRevisionID "707007539".
- Euclidean_shortest_path wikiPageWikiLink Algorithmica.
- Euclidean_shortest_path wikiPageWikiLink Category:Computational_geometry.
- Euclidean_shortest_path wikiPageWikiLink Category:Geometric_algorithms.
- Euclidean_shortest_path wikiPageWikiLink Computational_geometry.
- Euclidean_shortest_path wikiPageWikiLink Convex_polytope.
- Euclidean_shortest_path wikiPageWikiLink Dijkstras_algorithm.
- Euclidean_shortest_path wikiPageWikiLink Discrete_and_Computational_Geometry.
- Euclidean_shortest_path wikiPageWikiLink Euclidean_space.
- Euclidean_shortest_path wikiPageWikiLink File:Euclidean_Shortest_Path_KernelCAD_Screenshot.jpg.
- Euclidean_shortest_path wikiPageWikiLink Journal_of_the_ACM.
- Euclidean_shortest_path wikiPageWikiLink KernelCAD.
- Euclidean_shortest_path wikiPageWikiLink NP-hardness.
- Euclidean_shortest_path wikiPageWikiLink Numerical_precision.
- Euclidean_shortest_path wikiPageWikiLink Polyhedron.
- Euclidean_shortest_path wikiPageWikiLink SIAM_Journal_on_Computing.
- Euclidean_shortest_path wikiPageWikiLink Shortest_path_problem.
- Euclidean_shortest_path wikiPageWikiLink Springer_Science+Business_Media.
- Euclidean_shortest_path wikiPageWikiLink Symposium_on_Computational_Geometry.
- Euclidean_shortest_path wikiPageWikiLink Time_complexity.
- Euclidean_shortest_path wikiPageWikiLink Visibility_graph.
- Euclidean_shortest_path wikiPageWikiLink Weighted_region_problem.
- Euclidean_shortest_path wikiPageWikiLinkText "Euclidean shortest path".
- Euclidean_shortest_path wikiPageWikiLinkText "shortest path".
- Euclidean_shortest_path wikiPageUsesTemplate Template:Citation.
- Euclidean_shortest_path wikiPageUsesTemplate Template:Combin-stub.
- Euclidean_shortest_path wikiPageUsesTemplate Template:Geometry-stub.
- Euclidean_shortest_path wikiPageUsesTemplate Template:Reflist.
- Euclidean_shortest_path subject Category:Computational_geometry.
- Euclidean_shortest_path subject Category:Geometric_algorithms.
- Euclidean_shortest_path hypernym Problem.
- Euclidean_shortest_path type Area.
- Euclidean_shortest_path type Disease.
- Euclidean_shortest_path type Algorithm.
- Euclidean_shortest_path type Area.
- Euclidean_shortest_path type Combinatoric.
- Euclidean_shortest_path comment "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.".
- Euclidean_shortest_path label "Euclidean shortest path".
- Euclidean_shortest_path sameAs Q5406126.
- Euclidean_shortest_path sameAs m.02qwx_0.
- Euclidean_shortest_path sameAs Q5406126.
- Euclidean_shortest_path wasDerivedFrom Euclidean_shortest_path?oldid=707007539.
- Euclidean_shortest_path depiction Euclidean_Shortest_Path_KernelCAD_Screenshot.jpg.
- Euclidean_shortest_path isPrimaryTopicOf Euclidean_shortest_path.