Balancing Degree, Diameter, and Weight in Euclidean Spanners Academic Article uri icon


  • In a seminal STOC'95 paper, Arya et al. 4 devised a construction that for any set S of n points in \mathbbR^d and any ε> 0, provides a (1+ ε)-spanner with diameter O (log n), weight O (log 2 n) w (MST (S)), and constant maximum degree. Another construction of 4 provides a (1+ ε)- spanner with O (n) edges and diameter α (n), where α stands for the inverse-Ackermann function. Das and Narasimhan 12 devised a construction with constant maximum degree and weight O (w (MST (S))), but whose diameter may be arbitrarily large. In another construction by Arya et al. 4 there is diameter O (log n) and weight O (log n) w (MST (S)), but it may have arbitrarily large maximum degree. These constructions fail to address situations in which we are prepared to compromise on one of the parameters, but cannot afford it to be arbitrarily large. In this paper we devise a novel unified construction that trades between …

publication date

  • September 6, 2010