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.

Bio:

Prosenjit Bose received his B. Math (1990) and M. Math (1991) in Computer Science and Combinatorics from the University of Waterloo, Canada. He completed his Ph.D. (1994) in Computer Science at McGill University, Canada, where he received the D.W. Ambridge Award as the outstanding Ph.D. graduate. Currently, he is a full professor at the School of Computer Science and the associate dean for research in the Faculty of Science at Carleton University, Canada. He has received several research and teaching awards. His main research area is applied geometric computing. He has published over 200 journal and conference papers in this area.