On the spanning ratio of partial Delaunay triangulation
Florentin Neumann, Hannes Frey · 2012
Partial Delaunay triangulation (PDT) is a well-known subgraph construction that has already been used for years in the context of geographic routing and topology control. So far, it has been unknown if partial Delaunay triangulation is a network spanner. Network spanners are those subgraph constructions which maintain the length of the shortest path between any pair of nodes up to a constant factor. This factor is also referred to as the spanning ratio. In this work we prove that partial Delaunay triangulation is a network spanner for unit disk graphs. Furthermore, from our proof follows immediately that the spanning ratio of PDT is less than or equal to 1+√5/4 π2.