License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.22
URN: urn:nbn:de:0030-drops-94857
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9485/
Go to the corresponding LIPIcs Volume Portal

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

Improved Routing on the Delaunay Triangulation

pdf-format:
LIPIcs-ESA-2018-22.pdf (1 MB)

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

BibTeX - Entry

@InProceedings{bonichon_et_al:LIPIcs:2018:9485,
  author =	{Nicolas Bonichon and Prosenjit Bose and Jean-Lou De Carufel and Vincent Despr{\'e} and Darryl Hill and Michiel Smid},
  title =	{{Improved Routing on the Delaunay Triangulation}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9485},
  URN =		{urn:nbn:de:0030-drops-94857},
  doi =		{10.4230/LIPIcs.ESA.2018.22},
  annote =	{Keywords: Delaunay, local routing, geometric, graph}
}

Keywords: Delaunay, local routing, geometric, graph
Collection: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue Date: 2018
Date of publication: 14.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI