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 contributionAcademicpeer-review

1 Citation (Scopus)
5 Downloads (Pure)

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 ϵ > 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(n2 log n+hn2+ ϵ-1hn). It can be improved to O(n2 + ϵ-1n) for simple polygons.

Original languageEnglish
Title of host publication28th International Symposium on Algorithms and Computation, ISAAC 2017
EditorsY. Okamoto, T. Tokuyama
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages13
ISBN (Electronic)9783959770545
DOIs
Publication statusPublished - 1 Dec 2017
Externally publishedYes
Event28th International Symposium on Algorithms and Computation (ISAAC 2017) - Phuket, Thailand
Duration: 9 Dec 201712 Dec 2017
Conference number: 28
http://aiat.in.th/isaac2017/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume92
ISSN (Print)1868-8969

Conference

Conference28th International Symposium on Algorithms and Computation (ISAAC 2017)
Abbreviated titleISAAC 2017
CountryThailand
CityPhuket
Period9/12/1712/12/17
Internet address

Keywords

  • Polygonal domains
  • Routing scheme
  • Small stretch
  • Yao graph

Fingerprint Dive into the research topics of 'Routing in polygonal domains'. Together they form a unique fingerprint.

  • Cite this

    Banyassady, B., Chiu, M. K., Korman, M., Mulzer, W., van Renssen, A., Roeloffzen, M., Seiferth, P., Stein, Y., Vogtenhuber, B., & Willert, M. (2017). Routing in polygonal domains. In Y. Okamoto, & T. Tokuyama (Eds.), 28th International Symposium on Algorithms and Computation, ISAAC 2017 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 92). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ISAAC.2017.10