Name
Abstract | ||
|---|---|---|
For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the L-1 geodesic diameter in O(n(2)+h(4)) time and the L-1 geodesic center in O((n(4)+n(2) h(4))alpha(n)) time, where alpha(.) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in O(n(7.)(73)) or O(n(7)(h+log n)) time, and compute the geodesic center in O(n(12+is an element of)) time. Therefore, our algorithms are much faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L-1 shortest paths in polygonal domains. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.4230/LIPIcs.STACS.2016.14 | Leibniz International Proceedings in Informatics |
Keywords | DocType | Volume |
geodesic diameter,geodesic center,shortest paths,polygonal domains,L-1 metric | Journal | 47 |
Issue | ISSN | Citations |
3 | 1868-8969 | 0 |
PageRank | References | Authors |
0.34 | 0 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sang Won Bae | 1 | 189 | 31.53 |
| Matias Korman | 2 | 178 | 37.28 |
| Joseph S.B. Mitchell | 3 | 4329 | 428.84 |
| Yoshio Okamoto | 4 | 170 | 28.50 |
| Valentin Polishchuk | 5 | 252 | 34.51 |
| Haitao Wang | 6 | 157 | 20.13 |