Prosenjit Bose, Carleton University, Canada

Event Details
  • Date/Time:
    • Thursday April 5, 2012
      5:30 pm
  • Location: Klaus 1116
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:


Summary Sentence: Competitive Routing on a Variant of the Delaunay Triangulation

Full Summary: No summary paragraph submitted.

Title: Competitive Routing on a Variant of the Delaunay Triangulation

Abstract: A subgraph H of a weighted graph G is a t-spanner of G provided that for every edge xy in G, the weight of the shortest path between x and y in H is at most t times the weight of xy. It is known that the Delaunay triangulation of a point set P (where the empty region is an equilateral triangle) is a 2-spanner of the complete Euclidean graph. We present a new and simple proof of this spanning ratio that allows us to route competitively on this graph. Specifically, we present a deterministic local routing scheme that is guaranteed to find a short path between any pair of vertices in this Delaunay triangulation. We guarantee that the length of the path is at most 5/sqrt(3) times the Euclidean distance between the pair of vertices. Moreover, we show that no local routing scheme can achieve a better competitive spanning ratio thereby implying that our routing scheme is optimal. This is somewhat surprising since the spanning ratio is 2.

Additional Information

In Campus Calendar

College of Computing, School of Computer Science, ARC

Invited Audience
No audiences were selected.
No keywords were submitted.
  • Created By: Elizabeth Ndongi
  • Workflow Status: Published
  • Created On: Mar 28, 2012 - 12:24pm
  • Last Updated: Oct 7, 2016 - 9:58pm