Euclidean spanners

Abstract

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 tot al 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 fiir Informatik, D-66123 Saarbrucken, Germany. Email: {arya, michiel}@mpi-sb. mpg. de. Supported by the ESPRIT Basic Research Actions Program, under contract No. 7141 (project ALCOM 11). t Math Sciences Dept., The University of Memphis, Memphis, TN 38152. Supported in part by NSF Grant CCR9306822. E-mail: dasg@next 1.msci .memst . edu. i Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland. Partially supported by NSF Grant CCR-93107O5. This work was done while visiting the Max-Planck-Institut fiir Informatik, Saarbriicken. E-mail: mount @cs. umd. edu. SQue~Tech, IIIC., 7600A Leesburg Pike, Falls Church, VA 22043. This work was done while visiting the Max-Planck-Institut fiir Informatik, Saarbriicken. E-mail: jsalowet!nvl, army .mil. Permission to copy without fee all or part of thk material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyri ht notice and the title of thq publication and, is date appear, a#notice is given that copyt~isby~n,sslon of the Ass@ationof Computing Machinery. o cop otherwise, or to republish, requires a fee ancf/or speci ic permission. STOC’ 95, Las Vegas, Nevada, USA @ 1995 ACM 0-89791 -718-9/95/0005..$3.50 properties. We achieve these results in large part because of a new structure, called the dumbbell tree which provides a method of decomposing a spanner into a constant number of trees, so that each of the O(n2) spanner paths is mapped entirely to a path in one of these trees.