We study the average competitive ratio of on-line spanning trees with
the same distribution of points in the Euclidean plane. We show a dist
ribution of n points such that the average competitive ratio of on-lin
e spanning trees by any on-line algorithm cannot be less than 1/4 ln n
- 1/2. (C) 1997 Elsevier Science B.V.