DISPROOFS OF GENERALIZED GILBERT-POLLAK CONJECTURE ON THE STEINER RATIO IN 3 OR MORE DIMENSIONS

The Gilbert-Pollak conjecture, posed in 1968, was the most important c onjecture in the area of ''Steiner trees.'' The ''Steiner minimal tree '' (SMT) of a point set P is the shortest network of ''wires'' which w ill suffice to ''electrically'' interconnect P. The ''minimum spanning tree'' (MST) is the shortest such network when only intersite line se gments are permitted. The generalized GP conjecture stated that rho(d) = inf(p subset of Rd)(l(SMT)(P)/l(MST)(P)) was achieved when P was th e vertices of a regular d-simplex. It was showed previously that the c onjecture is true for d = 2 and false for 3 less than or equal to d le ss than or equal to 9. We settle remaining cases completely in this pa per. Indeed, we show that any point set achieving rho(d) must have car dinality growing at least exponentially with d. The real question now is: What are the true minimal-rho point sets? This paper introduces th e ''d-dimensional sausage'' point sets, which may have a lit to do wit h the answer. (C) 1996 Academic Press. Inc.