Worst-case bounds for subadditive geometric graphs
Marshall W. Bern, David Eppstein · 1993
We consider graphs such as the minimum spanning tree, minimum Steiner tree, minimum matching, and traveling salesman tour for n points in the d-dimensional unit cube. For each of these graphs, we show that the worst-case sum of the dth powers of edge lengths is O(log n). This is a consequence of a general "gap theorem": for any subadditive geometric graph, either the worst-case sum of edge lengths is O(n (d-1)/d ) and the sum of dth powers is O(log n), or the sum of edge lengths is #(n). We look more closely at some specific graphs: the worst-case sum of dth powers is O(1) for minimum matching, but #(log n) for traveling salesman tour, which answers a question of Snyder and Steele. 1. Introduction A worst-case, or a priori , bound on a geometric graph is a bound that depends only on the assumption that all vertices lie within a given container. Such a bound does not depend on the specific locations of vertices, nor on any probabilistic assumptions. Early papers especially ...