ONLINE STEINER TREES IN THE EUCLIDEAN PLANE

Suppose we are given a sequence of n points in the Euclidean plane, an d our objective is to construct, on-line, a connected graph that conne cts all of them, trying to minimize the total sum of lengths of its ed ges. The points appear one at a time, and at each step the on-line alg orithm must construct a connected graph that contains all current poin ts by connecting the new point to the previously constructed graph. Th is can be done by joining the new point (not necessarily by a straight line) to any point of the previous graph (not necessarily one of the given points). The performance of our algorithm is measured by its com petitive ratio: the supremum, over all sequences of points, of the rat io between the total length of the graph constructed by our algorithm and the total length of the best Steiner tree that connects all the po ints. There are known on-line algorithms whose competitive ratio is O( log n) even for all metric spaces, but the only lower bound known is o f [IW] for some contrived discrete metric space. Moreover, for the pla ne, on-line algorithms could have been more powerful and achieve a bet ter competitive ratio, and no nontrivial lower bounds for the best pos sible competitive ratio were known. Here we prove an almost tight lowe r bound of OMEGA(log n/log log n) 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 spac e of dimension greater than 2 as well.