Document Open Access Logo

Routing in Polygonal Domains

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.10.pdf
  • Filesize: 0.74 MB
  • 13 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Bahareh Banyassady, Man-Kwun Chiu, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein, Birgit Vogtenhuber, and Max Willert. Routing in Polygonal Domains. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.10

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

Subject Classification

Keywords
  • polygonal domains
  • routing scheme
  • small stretch,Yao graph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ittai Abraham and Cyril Gavoille. On approximate distance labels and routing schemes with affine stretch. In Proc. 25th DISC, pages 404-415, 2011. Google Scholar
  2. Takao Asano, Tetsuo Asano, Leonidas Guibas, John Hershberger, and Hiroshi Imai. Visibility of disjoint polygons. Algorithmica, 1(1-4):49-63, 1986. Google Scholar
  3. Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, and David Peleg. Improved routing strategies with succinct tables. JALG, 11(3):307-341, 1990. Google Scholar
  4. Reuven Bar-Yehuda and Bernard Chazelle. Triangulating disjoint Jordan chains. IJCGA, 4(04):475-481, 1994. Google Scholar
  5. Prosenjit Bose, Rolf Fagerberg, André van Renssen, and Sander Verdonschot. Optimal local routing on Delaunay triangulations defined by empty equilateral triangles. SICOMP, 44(6):1626 - 1649, 2015. Google Scholar
  6. Prosenjit Bose, Rolf Fagerberg, André van Renssen, and Sander Verdonschot. Competitive local routing with constraints. JoCG, 8(1):125-152, 2017. Google Scholar
  7. Shiri Chechik. Compact routing schemes with improved stretch. In Proc. PODC, pages 33-41, 2013. Google Scholar
  8. Lenore J Cowen. Compact routing with minimum stretch. JALG, 38(1):170-183, 2001. Google Scholar
  9. Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch factor. JALG, 46(2):97-114, 2003. Google Scholar
  10. Pierre Fraigniaud and Cyril Gavoille. Routing in trees. In Proc. 28th ICALP, pages 757-772, 2001. Google Scholar
  11. Silvia Giordano and Ivan Stojmenovic. Position based routing algorithms for ad hoc networks: A taxonomy. In Ad hoc wireless networking, pages 103-136. Springer-Verlag, 2004. Google Scholar
  12. Leonidas Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert E Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2(1-4):209-233, 1987. Google Scholar
  13. John Hershberger and Subhash Suri. An optimal algorithm for Euclidean shortest paths in the plane. SICOMP, 28(6):2215-2256, 1999. Google Scholar
  14. Barry Joe and Richard B Simpson. Corrections to Lee’s visibility polygon algorithm. BIT Numerical Mathematics, 27(4):458-473, 1987. Google Scholar
  15. Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth. Routing in unit disk graphs. In Proc. 12th LATIN, pages 536-548, 2016. Google Scholar
  16. Sanjiv Kapoor and SN Maheshwari. Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles. In Proc. 4th SoCG, pages 172-182, 1988. Google Scholar
  17. Sanjiv Kapoor, SN Maheshwari, and Joseph SB Mitchell. An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane. DCG, 18(4):377-383, 1997. Google Scholar
  18. Der-Tsai Lee. Visibility of a simple polygon. CGVIP, 22(2):207-221, 1983. Google Scholar
  19. Joseph SB Mitchell. A new algorithm for shortest paths among obstacles in the plane. AMAI, 3(1):83-105, 1991. Google Scholar
  20. Joseph SB Mitchell. Shortest paths among obstacles in the plane. IJCGA, 6(03):309-332, 1996. Google Scholar
  21. Mark H Overmars and Emo Welzl. New methods for computing visibility graphs. In Proc. 4th SoCG, pages 164-171, 1988. Google Scholar
  22. David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables. J. ACM, 36(3):510-530, 1989. Google Scholar
  23. Liam Roditty and Roei Tov. New routing techniques and their applications. In Proc. PODC, pages 23-32, 2015. Google Scholar
  24. Liam Roditty and Roei Tov. Close to linear space routing schemes. Distributed Computing, 29(1):65-74, 2016. Google Scholar
  25. Nicola Santoro and Ramez Khatib. Labelling and implicit routing in networks. The Computer Journal, 28(1):5-8, 1985. Google Scholar
  26. Micha Sharir and Amir Schorr. On shortest paths in polyhedral spaces. SICOMP, 15(1):193-215, 1986. Google Scholar
  27. James A Storer and John H Reif. Shortest paths in the plane with polygonal obstacles. J. ACM, 41(5):982-1012, 1994. Google Scholar
  28. Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, 51(6):993-1024, 2004. Google Scholar
  29. Mikkel Thorup and Uri Zwick. Compact routing schemes. In Proc. 13th SPAA, pages 1-10, 2001. Google Scholar
  30. Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1-24, 2005. Google Scholar
  31. Emo Welzl. Constructing the visibility graph for n-line segments in 𝒪(n²) time. IPL, 20(4):167-171, 1985. Google Scholar
  32. Chenyu Yan, Yang Xiang, and Feodor F Dragan. Compact and low delay routing labeling scheme for unit disk graphs. CGTA, 45(7):305-325, 2012. Google Scholar
  33. Andrew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SICOMP, 11(4):721-736, 1982. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact