Routing in Polygonal Domains

B. Banyassady, M.-K. Chiu, M. Korman, W. Mulzer, A. van Renssen, M. Roeloffzen, P. Seiferth, Y. Stein, B. Vogtenhuber, and M. Willert

Abstract:

We consider the problem of routing a data packet through the visibility graph of a polygonal domain $P$ with $n$ vertices and $h$ holes. We may preprocess $P$ to obtain a label and a routing table for each vertex. Then, we must be able to route a data packet between any two vertices $p$ and $q$ of $P$, where each step must use only the label of the target node $q$ and the routing table of the current node. For any fixed $\varepsilon > 0$, we present a routing scheme that always achieves a routing path that exceeds the shortest path by a factor of at most $1 + \varepsilon$. The labels have $\mathcal{O}(\log n)$ bits, and the routing tables are of size $\mathcal{O}((\varepsilon^{-1}+h)\log n)$. The preprocessing time is $\mathcal{O}(n^2\log n + hn^2+\varepsilon^{-1}hn)$. It can be improved to $\mathcal{O}(n^2+\varepsilon^{-1}n)$ for simple polygons.

Reference: B. Banyassady, M.-K. Chiu, M. Korman, W. Mulzer, A. van Renssen, M. Roeloffzen, P. Seiferth, Y. Stein, B. Vogtenhuber, and M. Willert. Routing in polygonal domains. In Y. Okamoto and T. Tokuyama, editors, 28th International Symposium on Algorithms and Computation (ISAAC 2017), volume 92 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1-10:13, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.