Worst-case bounds for subadditive geometric graphs.
M. Bern
and D. Eppstein.
9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 183–188,
doi:10.1145/160985.161018.
For many geometric graph problems for points in the unit square, such as minimum spanning trees, matching, and traveling salesmen, the sum of edge lengths is O(sqrt n) and the sum of dth powers of edge lengths is O(log n). We provide a "gap theorem" showing that if these bounds do not hold for a class of graphs, both sums will instead be Omega(n). For traveling salesmen the O(log n) bound is tight but for some other graphs the sum of dth powers of edge lengths is O(1).