Name
Title | ||
|---|---|---|
Approximating minimum-cost polygonal paths of bounded number of links in weighted subdivisions |
Abstract | ||
|---|---|---|
This video illustrates the k-LinkSolver software for computing k-link shortest paths in weighted regions. The k-LinkSolver implements methods to find paths of length at most (1+ε) times the length of a shortest k-link path, for any fixed ε0, and having at most 2k−1 links. The methods implemented are an improvement over the previously known (1+ε)-approximation algorithms, which guarantee at most 5k−2 links. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1145/1137856.1137930 | Symposium on Computational Geometry 2013 |
Keywords | Field | DocType |
minimum-cost polygonal path,bounded number,k-linksolver software,weighted region,approximation algorithm,k-link shortest path,shortest k-link path,weighted subdivision,delaunay triangulation,quadtree,voronoi diagram,shortest path,memory management | Discrete mathematics,Polygon,Combinatorics,Computer science,Constrained Shortest Path First,Floyd–Warshall algorithm,Voronoi diagram,Bounded function,Quadtree,K shortest path routing,Delaunay triangulation | Conference |
ISBN | Citations | PageRank |
1-59593-340-9 | 1 | 0.37 |
References | Authors | |
6 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ovidiu Daescu | 1 | 276 | 45.78 |
| Joseph S.B. Mitchell | 2 | 4329 | 428.84 |
| Simeon Ntafos | 3 | 274 | 31.82 |
| James D. Palmer | 4 | 53 | 14.93 |
| Chee-Keng Yap | 5 | 1996 | 395.32 |