On-line Steiner trees in the Euclidean plane

Suppose we are given a sequence of n points v₁, . . . , v_n in the Euclidean plane, and our objective is to construct, on-line, a connected graph that connects all of them, trying to minimize the total sum of lengths of its edges. We assume that the points appear one at a time, v_i arriving at step i. At the end of step i, the on-line algorithm must construct a connected graph T_i that contains the points v₁, . . . , v_i by connecting the new point v_i to the previously constructed graph T_i-1. This can be done by joining v_i (not necessarily by a straight line) to any point of T_i-1, which need not necessarily be one of the previously given points v_j. The performance of our algorithm is measured by its competitive ratio: the supremum, over all sequences v₁, . . . , v_n as above, of the ratio between the total length of the graph constructed by our algorithm and the total length of the best Steiner tree that connects all the points v₁, . . . , v_n. There are known on-line algorithms whose competitive ratio is O(log n), but there is no known nontrivial lower bound for the best possible competitive ratio. Here we prove that the upper bound is almost tight by establishing an Ω(log n/log log n) lower bound for the competitive ratio of any on-line algorithm. The lower bound holds for deterministic algorithms as well as for randomized ones, and obviously holds in any Euclidean space of dimension greater than 2 as well.