Name
Abstract | ||
|---|---|---|
We consider the well-known geometric problem of determining shortest paths between pairs of points on a polyhedral surface P, where P consists of triangular faces with positive weights assigned to them. The cost of a path in P is defined to be the weighted sum of Euclidean lengths of the sub-paths within each face of P. We present query algorithms that compute approximate distances and/or approximate shortest paths on P. Our all-pairs query algorithms take as input an approximation parameter ε∈(0,1) and a query time parameter $\mathfrak{q}$, in a certain range, and build a data structure $\mathrm{APQ}(P,\varepsilon;\mathfrak{q})$, which is then used for answering ε-approximate distance queries in $O(\mathfrak{q})$time. As a building block of the $\mathrm{APQ}(P,\varepsilon;\mathfrak{q})$data structure, we develop a single-source query data structure SSQ(a;P,ε) that can answer ε-approximate distance queries from a fixed point a to any query point on P in logarithmic time. Our algorithms answer shortest path queries in weighted surfaces, which is an important extension, both theoretically and practically, to the extensively studied Euclidean distance case. In addition, our algorithms improve upon previously known query algorithms for shortest paths on surfaces. The algorithms are based on a novel graph separator algorithm introduced and analyzed here, which extends and generalizes previously known separator algorithms. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/s00454-009-9204-0 | Discrete and Computational Geometry |
Keywords | Field | DocType |
Shortest path,Query algorithm,Separator,Weighted polyhedral surface | Euclidean geometry,Logarithm,Fixed point,K shortest path routing,Data structure,Discrete mathematics,Topology,Combinatorics,Shortest path problem,Euclidean distance,Algorithm,Mathematics,Euclidean shortest path | Journal |
Volume | Issue | ISSN |
44 | 4 | 1432-0444 |
Citations | PageRank | References |
15 | 0.76 | 34 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lyudmil Aleksandrov | 1 | 121 | 8.60 |
| Hristo N. Djidjev | 2 | 154 | 16.61 |
| Hua Guo | 3 | 80 | 3.62 |
| Anil Maheshwari | 4 | 869 | 104.47 |
| Doron Nussbaum | 5 | 89 | 13.49 |
| Jörg-Rüdiger Sack | 6 | 1099 | 166.07 |