Document Open Access Logo

Improved Routing on the Delaunay Triangulation

Authors Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel, Vincent Despré, Darryl Hill, Michiel Smid

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.22.pdf
  • Filesize: 1.33 MB
  • 13 pages

Document Identifiers

Author Details

Nicolas Bonichon
  • Université de Bordeaux, LaBRI, UMR 5800, F-33400 Talence, France
Prosenjit Bose
  • Carleton University, 1125 Colonel By Dr, Ottawa, ON, Canada
Jean-Lou De Carufel
  • University of Ottawa, 800 King Edward Ave, Ottawa, ON, Canada
Vincent Despré
  • Team Gamble, INRIA Nancy, 54600 Villers-lès-Nancy, France
Darryl Hill
  • Carleton University, 1125 Colonel By Dr, Ottawa, ON, Canada
Michiel Smid
  • Carleton University, 1125 Colonel By Dr, Ottawa, ON, Canada

Funding

This work was supported by the National Sciences and Engineering Research Council of Canada (NSERC) and by the French ANR grant ASPAG (ANR-17-CE40-0017)

Cite As Get BibTex

Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel, Vincent Despré, Darryl Hill, and Michiel Smid. Improved Routing on the Delaunay Triangulation. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.22

Abstract

A geometric graph G=(P,E) is a set of points in the plane and edges between pairs of points, where the weight of an edge is equal to the Euclidean distance between its two endpoints. In local routing we find a path through G from a source vertex s to a destination vertex t, using only knowledge of the current vertex, its incident edges, and the locations of s and t. We present an algorithm for local routing on the Delaunay triangulation, and show that it finds a path between a source vertex s and a target vertex t that is not longer than 3.56|st|, improving the previous bound of 5.9|st|.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Paths and connectivity problems
  • Mathematics of computing → Graph algorithms
Keywords
  • Delaunay
  • local routing
  • geometric
  • graph

Metrics

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

References

  1. Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel, Ljubomir Perković, and André van Renssen. Upper and lower bounds for online routing on Delaunay triangulations. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015, volume 9294 of Lecture Notes in Computer Science, pages 203-214. Springer Berlin Heidelberg, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_18.
  2. Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel, Ljubomir Perković, and André van Renssen. Upper and lower bounds for online routing on Delaunay triangulations. Discrete & Computational Geometry, 58(2):482-504, Sep 2017. URL: http://dx.doi.org/10.1007/s00454-016-9842-y.
  3. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Ljubomir Perković. Tight stretch factors for L₁ and L_∞ Delaunay triangulations. Computational Geometry, 48(3):237-250, 2015. URL: http://dx.doi.org/10.1016/j.comgeo.2014.10.005.
  4. Prosenjit Bose, Jean-Lou De Carufel, Stephane Durocher, and Perouz Taslakian. Competitive online routing on Delaunay triangulations. In R. Ravi and Inge Li Gørtz, editors, Algorithm Theory - SWAT 2014 - 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings, volume 8503 of Lecture Notes in Computer Science, pages 98-109. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-08404-6_9.
  5. Prosenjit Bose, Rolf Fagerberg, André van Renssen, and Sander Verdonschot. Competitive routing in the half-theta-6-graph. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, pages 1319-1328. SIAM, 2012. URL: http://dl.acm.org/citation.cfm?id=2095116.2095220.
  6. Prosenjit Bose and Pat Morin. Online routing in triangulations. In Algorithms and Computation, volume 1741 of Lecture Notes in Computer Science, pages 113-122. Springer Berlin Heidelberg, 1999. URL: http://dx.doi.org/10.1007/3-540-46632-0_12.
  7. L. Paul Chew. There is a planar graph almost as good as the complete graph. In Proceedings of the Second Annual Symposium on Computational Geometry, SCG '86, pages 169-177, New York, NY, USA, 1986. ACM. URL: http://dx.doi.org/10.1145/10515.10534.
  8. L. Paul Chew. There are planar graphs almost as good as the complete graph. Journal of Computer and System Sciences, 39(2):205-219, 1989. URL: http://dx.doi.org/10.1016/0022-0000(89)90044-5.
  9. Michael Dennis, Ljubomir Perković, and Duru Türkoglu. The stretch factor of hexagon-Delaunay triangulations. CoRR, abs/1711.00068, 2017. URL: http://arxiv.org/abs/1711.00068.
  10. David P. Dobkin, Steven J. Friedman, and Kenneth J. Supowit. Delaunay graphs are almost as good as complete graphs. Discrete &Computational Geometry, 5(1):399-407, 1990. URL: http://dx.doi.org/10.1007/BF02187801.
  11. J. Mark Keil and Carl A. Gutwin. Classes of graphs which approximate the complete euclidean graph. Discrete &Computational Geometry, 7(1):13-28, 1992. URL: http://dx.doi.org/10.1007/BF02187821.
  12. Giri Narasimhan and Michiel Smid. Geometric Spanner Networks. Cambridge University Press, New York, NY, USA, 2007. Google Scholar
  13. Ge Xia. Improved upper bound on the stretch factor of Delaunay triangulations. In Proceedings of the Twenty-seventh Annual Symposium on Computational Geometry, SoCG '11, pages 264-273, New York, NY, USA, 2011. ACM. URL: http://dx.doi.org/10.1145/1998196.1998235.
  14. Ge Xia and Liang Zhang. Toward the tight bound of the stretch factor of Delaunay triangulations. In Proceedings of the Canadian Conference on Computational Geometry, CCCG '11, 2011. 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