2026-07-21T14:19:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8237 2024-03-06T10:41:46Z ddc:004 open_access

Routing in Polygonal Domains Banyassady, Bahareh Chiu, Man-Kwun Korman, Matias Mulzer, Wolfgang van Renssen, André Roeloffzen, Marcel Seiferth, Paul Stein, Yannik Vogtenhuber, Birgit Willert, Max polygonal domains routing scheme small stretch,Yao graph 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 eps > 0, we pre ent a routing scheme that always achieves a routing path that exceeds the shortest path by a factor of at most 1 + eps. The labels have O(log n) bits, and the routing tables are of size O((eps^{-1} + h) log n). The preprocessing time is O(n^2 log n + hn^2 + eps^{-1}hn). It can be improved to O(n 2 + eps^{-1}n) for simple polygons. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bahareh Banyassady and Man-Kwun Chiu and Matias Korman and Wolfgang Mulzer and André van Renssen and Marcel Roeloffzen and Paul Seiferth and Yannik Stein and Birgit Vogtenhuber and Max Willert 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.10 urn:nbn:de:0030-drops-82379 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.10 eng https://creativecommons.org/licenses/by/3.0/legalcode