@inproceedings{8ef6e7a2da8043448ba46b0b29caff4e,

title = "Routing in Polygonal Domains",

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 + . The labels have $O(log n)$ bits, and the routing tables are of size $O((-1+h)log n)$. The preprocessing time is $O(n^2log n + hn^2+-1hn)$. It can be improved to $O(n^2+-1n)$ for simple polygons.",

author = "Bahareh Banyassady and Man-Kwun Chiu and Matias Korman and Wolfgang Mulzer and Renssen, {Andr{\'e} van} and Marcel Roeloffzen and Paul Seiferth and Yannik Stein and Birgit Vogtenhuber and Max Willert",

year = "2017",

doi = "10.4230/LIPIcs.ISAAC.2017.10",

language = "English",

isbn = "978-3-95977-054-5",

volume = "92",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "10:1--10:13",

editor = "Yoshio Okamoto and Takeshi Tokuyama",

booktitle = "28th International Symposium on Algorithms and Computation (ISAAC 2017)",

address = "Germany",

note = "28th International Symposium on Algorithms and Computation : ISAAC 2017 ; Conference date: 09-12-2017 Through 12-12-2017",

}