On the Spanning Ratio of Partial Delaunay Triangulation

Partial Delaunay Triangulation (PDT) is a well-known sub-graph 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 sub-graph 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 paper, the authors prove that partial Delaunay triangulation is a network spanner for unit disk graphs.