LARGEST MINIMAL RECTILINEAR STEINER TREES FOR A SET OF N POINTS ENCLOSED IN A RECTANGLE WITH GIVEN PERIMETER

Suppose P is a set of points in the plane with rectilinear distance. Let ls(P) denote the length of a Steiner minimal tree for P. Let lr(P) denote the semiperimeter of the smallest rectangle with vertical and horizontal lines which encloses P. It is well known that ls(P) ≥ lr(P) for ∣P∣ ≥ 3 where ∣P∣ denotes the cordinality of P. In designing placement algorithms for printed circuits, lr(P) has been used as an estimate of ls(P) when ∣P∣ is small. Therefore, it is of some interest to know the value of (Formula Presented.) In this paper we show ρn tends to (√n+1)/2 and we give the exact value of ρn for n ≤ 10. Copyright © 1979 Wiley Periodicals, Inc., A Wiley Company