Premium
The largest minimal rectilinear steiner trees for a set of n points enclosed in a rectangle with given perimeter
Author(s) -
Chung F. R. K.,
Hwang F. K.
Publication year - 1979
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230090103
Subject(s) - rectangle , combinatorics , steiner tree problem , mathematics , perimeter , plane (geometry) , set (abstract data type) , value (mathematics) , discrete mathematics , geometry , computer science , statistics , programming language
Suppose P is a set of points in the plane with rectilinear distance. Let l s (P) denote the length of a Steiner minimal tree for P. Let l r (P) denote the semiperimeter of the smallest rectangle with vertical and horizontal lines which encloses P. It is well known that l s (P) ≥ l r (P) for ∣P∣ ≥ 3 where ∣P∣ denotes the cordinality of P. In designing placement algorithms for printed circuits, l r (P) has been used as an estimate of l s (P) when ∣P∣ is small. Therefore, it is of some interest to know the value of\documentclass{article}\pagestyle{empty}\begin{document}$$ \rho _n \equiv \mathop {Max}\limits_{\left| P \right| = n} \frac{\ell{_s (P)}}{\ell{_r (P)}}. $$\end{document}In this paper we show ρ n tends to (√n+1)/2 and we give the exact value of ρ n for n ≤ 10.