event
Prosenjit Bose, Carleton University, Canada
Primary tabs
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.
Status
-
Workflow Status:
Published -
Created By:
Elizabeth Ndongi -
Created:
03/28/2012 -
Modified By:
Fletcher Moore -
Modified:
10/07/2016
Categories
Keywords
Target Audience