Ad Hoc Wireless Research - Delaunay
Mirela Damian & Kory Kirk
Villanova University - Computer Science

Delaunay Triangulation in Ad Hoc Networks

In this research we experimentally try to determine whether a particular conjecture concerning the Delaunay triangulation of a random point set is true or false. It has been shown in past research that a lower bound value for the stretch factor for a Delaunay triangulation is approximately π/2. The conjecture we set out to disprove is whether the Delaunay triangulation is a π/2 spanner. We also specialize this conjecture for points in convex position and show that, for two points that lie on the convex hull of the Delaunay triangulation, the shortest path connecting these points is less than or equal to the direct distance between those same two points times π/2.