LIPIcs.ISAAC.2017.18.pdf
- Filesize: 0.6 MB
- 12 pages
Document
Routing on the Visibility Graph
Authors
-
Part of:
Volume:
28th International Symposium on Algorithms and Computation (ISAAC 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-12-07
Cite As Get BibTex
Prosenjit Bose, Matias Korman, André van Renssen, and Sander Verdonschot. Routing on the Visibility Graph. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 18:1-18:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ISAAC.2017.18
Abstract
We consider the problem of routing on a network in the presence of line segment constraints (i.e., obstacles that edges in our network are not allowed to cross). Let P be a set of n vertices in the plane and let S be a set of line segments between the vertices in P, with no two line segments intersecting properly. We present two 1-local O(1)-memory routing algorithms on the visibility graph of P with respect to a set of constraints S (i.e., the algorithms never look beyond the direct neighbours of the current location and store only a constant amount of information). Contrary to all existing routing algorithms, our routing algorithms do not require us to compute a plane subgraph of the visibility graph in order to route on it.
Subject Classification
Keywords
- Routing
- constraints
- visibility graph
- Theta-graph
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Prosenjit Bose, Rolf Fagerberg, André van Renssen, and Sander Verdonschot. On plane constrained bounded-degree spanners. In LATIN, volume 7256 of LNCS, pages 85-96, 2012.
-
Prosenjit Bose, Rolf Fagerberg, André van Renssen, and Sander Verdonschot. Competitive local routing with constraints. Journal of Computational Geometry, 8(1):125-152, 2017.
-
Prosenjit Bose, Matias Korman, André van Renssen, and Sander Verdonschot. Constrained routing between non-visible vertices. In COCOON, 2017.
-
Prosenjit Bose and André van Renssen. Upper bounds on the spanning ratio of constrained theta-graphs. In LATIN, volume 8392 of LNCS, pages 108-119, 2014.
-
Ken Clarkson. Approximation algorithms for shortest path motion planning. In STOC, pages 56-65, 1987.
-
Gautam Das. The visibility graph contains a bounded-degree spanner. In CCCG, pages 70-75, 1997.
-
Sudip Misra, Subhas Chandra Misra, and Isaac Woungang. Guide to Wireless Sensor Networks. Springer, 2009.
-
Harald Räcke. Survey on oblivious routing strategies. In Mathematical Theory and Computational Practice, volume 5635 of LNCS, pages 419-429, 2009.