Lower bound for sparse Euclidean spanners
Pankaj K. Agarwal, Yusu Wang, Peng Yin · 2005
Given a one-dimensional graph ¢ such that any two consecutive nodes are unit distance away, and such that the minimum number of links between any two nodes (the diameter of ¢ ) is £¥¤§¦©¨����� � , we prove an ��¤§��¦�¨�������¦�¨���¦©¨����� � lower bound on the sum of lengths of all the edges (i.e., the weight of ¢). The problem is a variant of the widely studied partial sum problem. This in turn provides a lower bound on Euclidean spanner graphs with small diameter and low weight, showing that the upper bound from [1] is almost tight. 1