TY - JOUR A1 - Banyassady, Bahareh A1 - Chiu, Man-Kwun A1 - Korman, Matias A1 - Mulzer, Wolfgang A1 - van Renssen, André A1 - Roeloffzen, Marcel A1 - Seiferth, Paul A1 - Stein, Yannik A1 - Vogtenhuber, Birgit A1 - Willert, Max T1 - Routing in polygonal domains JF - Computational Geometry, Theory and Applications N2 - 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 of P. 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 epsilon > 0, we present a routing scheme that always achieves a routing path whose length exceeds the shortest path by a factor of at most 1 + epsilon. The labels have O(log n) bits, and the routing tables are of size O(((epsilon^-1)+h)log n). The preprocessing time is O((n^2)log n). It can be improved to O(n^2) for simple polygons. Y1 - 2019 U6 - https://doi.org/10.1016/j.comgeo.2019.101593 VL - 87 PB - Elsevier ER -