TY - CONF T1 - M.H.M: Euclidean spanners: short, thin, and lanky T2 - In: 27th ACM Symposium on Theory of Computing Y1 - 1995 A1 - Arya,Sunil A1 - Dast,Gautam A1 - Mount, Dave A1 - Salowe,Jeffrey S. A1 - Smid,Michiel AB - 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, JA - In: 27th ACM Symposium on Theory of Computing PB - ACM press ER -