Euclidean spanners: short, thin, and lanky
Sunil Arya, Gautam Das, David M. Mount, Jeffrey S. Salowe, Michiel Smid · 1995
Euclidean spanners are important data structures in geometric algorithm design, because they provide a means of approximating the complete Euclidean graph with only O(n) edges, so that the shortest path length between each pair of points is not more than a constant factor longer than the Euclidean distance between the points. In many applications of spanners, it is important that the spanner possess a number of additional properties: low total edge weight, bounded degree, and low diameter. Existing research on spanners has considered one property or the other. We show that it is possible to build spanners in optimal O(n log n) time and O(n) space that achieve optimal or near optimal tradeoffs between all combinations of these Max-Planck-Institut fur Informatik, D-66123 Saarbrucken, Germany. Email: farya,[email protected]. Supported by the ESPRIT Basic Research Actions Program, under contract No. 7141 (project ALCOM II). y Math Sciences Dept., The University of Memphis, Memp...