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(\cdot)$ 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+\epsilon})$ 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 | Venue | Field |
|---|---|---|
2015 | CoRR | Inverse,Topology,Binary logarithm,Polygon,Combinatorics,Ackermann function,Vertex (geometry),Euclidean geometry,Geodesic,Mathematics |
DocType | Volume | Citations |
Journal | abs/1512.07160 | 1 |
PageRank | References | Authors |
0.38 | 15 | 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 | 538 | 36.95 |