Routing in Polygonal Domains

Bahareh Banyassady, Man-Kwun Chiu, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein, Birgit Vogtenhuber, Max Willert

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


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.
Original languageEnglish
Title of host publication28th International Symposium on Algorithms and Computation (ISAAC 2017)
EditorsYoshio Okamoto, Takeshi Tokuyama
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Print)978-3-95977-054-5
Publication statusPublished - 2017
Event28th International Symposium on Algorithms and Computation: ISAAC 2017 - Phuket, Thailand
Duration: 9 Dec 201712 Dec 2017

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik


Conference28th International Symposium on Algorithms and Computation


Dive into the research topics of 'Routing in Polygonal Domains'. Together they form a unique fingerprint.

Cite this