Name
Abstract | ||
|---|---|---|
We consider the classical geometric problem of determining shortest paths between pairs of points lying on a weighted polyhedral surface P consisting of n triangular faces. We present query algorithms that compute approximate distances and/or approximate (weighted) shortest paths. Our algorithm takes as input an approximation parameter ε∈(0,1) and a query time parameter $\mathfrak{q}$ and builds a data structure which is then used for answering ε-approximate distance queries in $O(\mathfrak{q})$ time. This algorithm is source point independent and improves significantly on the best previous solution. For the case where one of the query points is fixed we build a data structure that can answer ε-approximate distance queries to any query point in P in $O(\log\frac{1}{\varepsilon})$ time. This is an improvement upon the previously known solution for the Euclidean fixed source query problem. Our algorithm also generalizes the setting from previously studied unweighted polyhedral to weighted polyhedral surfaces of arbitrary genus. Our solutions are based on a novel graph separator algorithm introduced here which extends and generalizes previously known separator algorithms. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11821069_9 | MFCS |
Keywords | Field | DocType |
separator algorithm,approximate shortest path query,approximate distance,shortest path,query point,novel graph separator algorithm,approximate distance query,query time parameter,query algorithm,euclidean fixed source query,data structure,weighted polyhedral surface,shortest path algorithm | Graph,Discrete mathematics,Data structure,Combinatorics,Database query,Shortest path problem,Steiner point,Polyhedron,Point source,Euclidean geometry,Mathematics | Conference |
Volume | ISSN | ISBN |
4162 | 0302-9743 | 3-540-37791-3 |
Citations | PageRank | References |
6 | 0.47 | 14 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lyudmil Aleksandrov | 1 | 121 | 8.60 |
| Hristo N. Djidjev | 2 | 154 | 16.61 |
| Hua Guo | 3 | 10 | 1.27 |
| Anil Maheshwari | 4 | 869 | 104.47 |
| Doron Nussbaum | 5 | 89 | 13.49 |
| Jörg-Rüdiger Sack | 6 | 1099 | 166.07 |