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

doi:10.4230/LIPIcs.ISAAC.2017.10

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 proceeding › Conference contribution › Academic › peer-review

2 Citations (Scopus)

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

Original language	English
Title of host publication	28th International Symposium on Algorithms and Computation, ISAAC 2017
Editors	Y. Okamoto, T. Tokuyama
Place of Publication	Dagstuhl
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages	13
ISBN (Electronic)	9783959770545
DOIs	https://doi.org/10.4230/LIPIcs.ISAAC.2017.10
Publication status	Published - 1 Dec 2017
Externally published	Yes
Event	28th International Symposium on Algorithms and Computation (ISAAC 2017) - Phuket, Thailand Duration: 9 Dec 2017 → 12 Dec 2017 Conference number: 28 http://aiat.in.th/isaac2017/

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Volume	92
ISSN (Print)	1868-8969

Conference

Conference	28th International Symposium on Algorithms and Computation (ISAAC 2017)
Abbreviated title	ISAAC 2017
Country/Territory	Thailand
City	Phuket
Period	9/12/17 → 12/12/17
Internet address	http://aiat.in.th/isaac2017/

Keywords

Polygonal domains
Routing scheme
Small stretch
Yao graph

Access to Document

10.4230/LIPIcs.ISAAC.2017.10

publishers versionFinal published version, 723 KBLicence: CC BY

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

@inproceedings{d3cee450c4544bf2884570a940c7d584,

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 ϵ > 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.",

keywords = "Polygonal domains, Routing scheme, Small stretch, Yao graph",

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

year = "2017",

month = dec,

day = "1",

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

language = "English",

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

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

editor = "Y. Okamoto and T. Tokuyama",

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

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

url = "http://aiat.in.th/isaac2017/",

}

Banyassady, B, Chiu, MK, 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, Dagstuhl, 28th International Symposium on Algorithms and Computation (ISAAC 2017), Phuket, Thailand, 9/12/17. https://doi.org/10.4230/LIPIcs.ISAAC.2017.10

Routing in polygonal domains. / Banyassady, Bahareh; Chiu, Man Kwun; Korman, Matias et al.
28th International Symposium on Algorithms and Computation, ISAAC 2017. ed. / Y. Okamoto; T. Tokuyama. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 92).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Routing in polygonal domains

AU - Banyassady, Bahareh

AU - Chiu, Man Kwun

AU - Korman, Matias

AU - Mulzer, Wolfgang

AU - van Renssen, André

AU - Roeloffzen, Marcel

AU - Seiferth, Paul

AU - Stein, Yannik

AU - Vogtenhuber, Birgit

AU - Willert, Max

N1 - Conference code: 28

PY - 2017/12/1

Y1 - 2017/12/1

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. 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.

AB - 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.

KW - Polygonal domains

KW - Routing scheme

KW - Small stretch

KW - Yao graph

UR - http://www.scopus.com/inward/record.url?scp=85038595037&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2017.10

DO - 10.4230/LIPIcs.ISAAC.2017.10

M3 - Conference contribution

AN - SCOPUS:85038595037

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

BT - 28th International Symposium on Algorithms and Computation, ISAAC 2017

A2 - Okamoto, Y.

A2 - Tokuyama, T.

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl

T2 - 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Y2 - 9 December 2017 through 12 December 2017

ER -

Banyassady B, Chiu MK, Korman M, Mulzer W, van Renssen A, Roeloffzen M et al. Routing in polygonal domains. In Okamoto Y, Tokuyama T, editors, 28th International Symposium on Algorithms and Computation, ISAAC 2017. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2017. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.ISAAC.2017.10

Routing in polygonal domains

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this