DROPS

Document

DOI: 10.4230/LIPIcs.WADS.2025.9

Online Routing in Directed Yao₄^∞ Graphs

Authors: Prosenjit Bose, Jean-Lou De Carufel, and John Stuart

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

The x⃑{Yao₄^∞} and x⃑{Yao₄} graphs are two families of directed geometric graphs whose vertices are points in the plane, and each vertex has up to four outgoing edges. Consider a horizontal and a vertical line through each vertex v, defining four quadrants around v. Then v has an outgoing edge to the closest vertex in each of its four quadrants. When the distance is measured using the Euclidean norm, the resulting graph is the x⃑{Yao₄} graph, whereas with the L_∞-norm, we obtain the x⃑{Yao^{∞}₄} graph, which is a sub-graph of the well-known L_∞-Delaunay graph. In this paper, we provide a local routing algorithm with routing ratio at most 85.22 for x⃑{Yao^{∞}₄} graphs. Prior to this work, no constant spanning or routing ratios for x⃑{Yao₄^∞} graphs were previously known. Now, x⃑{Yao₄^∞} graphs are the sparsest family of directed planar graphs supporting a competitive local routing strategy. Furthermore, we show that no local routing algorithm for x⃑{Yao₄^∞} graphs can have a routing ratio lower than 7+√2≈ 8.41. Moreover, we prove that the spanning ratio is at least 5+√2≈ 6.41 in the worst case. The techniques we develop in this paper also allow us to prove lower bounds of 7-√3+√{5-2√3}≈ 6.51 and 7+√2 for the spanning and routing ratios of x⃑{Yao₄}, respectively.

Cite as

Prosenjit Bose, Jean-Lou De Carufel, and John Stuart. Online Routing in Directed Yao₄^∞ Graphs. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 9:1-9:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.WADS.2025.9,
  author =	{Bose, Prosenjit and De Carufel, Jean-Lou and Stuart, John},
  title =	{{Online Routing in Directed Yao₄^∞ Graphs}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{9:1--9:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.9},
  URN =		{urn:nbn:de:0030-drops-242404},
  doi =		{10.4230/LIPIcs.WADS.2025.9},
  annote =	{Keywords: Geometric Spanners, Yao Graphs, Local Routing Algorithms}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2024.14

Routing from Pentagon to Octagon Delaunay Graphs

Authors: Prosenjit Bose, Jean-Lou De Carufel, and John Stuart

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract

The standard Delaunay triangulation is a geometric graph whose vertices are points in the plane, and two vertices share an edge if they lie on the boundary of an empty disk. If the disk is replaced with a homothet of a fixed convex shape C, then the resulting graph is called a C-Delaunay graph. We study the problem of local routing in C-Delaunay graphs where C is a regular polygon having five to eight sides. In particular, we generalize the routing algorithm of Chew for square-Delaunay graphs (Chew. SCG 1986, 169-177) in order to obtain the following approximate upper bounds of 4.640, 6.429, 8.531 and 4.054 on the spanning and routing ratios for pentagon-, hexagon-, septagon-, and octagon-Delaunay graphs, respectively. The exact expression for the upper bounds of the routing ratio is Ψ(n):= √{1+((cos(2π/n)+n-1)/sin(2π/n))^2} (if n ∈ {5,6,7}), √{1+((cos(π/8)cos(3π/8)+3)/(cos(π/8)sin(3π/8)))^2} (if n = 8). We show that these bounds are tight for the output of our routing algorithm by providing a point set where these bounds are achieved. We also include lower bounds of 1.708 and 1.995 on the spanning and routing ratios of the pentagon-Delaunay graph. Our upper bounds yield a significant improvement over the previous routing ratio upper bounds for this problem, which previously sat at around 400 for the pentagon, septagon, and octagon as well as 18 for the hexagon. Our routing ratios also provide significant improvements over the previously best known spanning ratios for pentagon-, septagon- and octagon-Delaunay graphs, which were around 45.

Cite as

Prosenjit Bose, Jean-Lou De Carufel, and John Stuart. Routing from Pentagon to Octagon Delaunay Graphs. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.ISAAC.2024.14,
  author =	{Bose, Prosenjit and De Carufel, Jean-Lou and Stuart, John},
  title =	{{Routing from Pentagon to Octagon Delaunay Graphs}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.14},
  URN =		{urn:nbn:de:0030-drops-221411},
  doi =		{10.4230/LIPIcs.ISAAC.2024.14},
  annote =	{Keywords: Geometric Spanners, Generalized Delaunay Graphs, Local Routing Algorithms}
}

Search Results

Documents authored by Stuart, John

Online Routing in Directed Yao₄^∞ Graphs

Abstract

Cite as

Routing from Pentagon to Octagon Delaunay Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message