On Steiner minimal trees with \(L_ p\) distance (Q1186795): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Ding-Zhu Du / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Konrad Engel / rank | |||
Normal rank |
Revision as of 02:56, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On Steiner minimal trees with \(L_ p\) distance |
scientific article |
Statements
On Steiner minimal trees with \(L_ p\) distance (English)
0 references
28 June 1992
0 references
Let \(L\) be the plane with the distance \(d_ p((x_ 1,x_ 2),(y_ 1,y_ 2))=(| x_ 1-x_ 2|^ p+| y_ 1-y_ 2|^ p)^{1/p}\). Let \(P\) be a finite set of points in \(L_ p\) and let \(L_ s(P)\) be the length of a Steiner minimal tree, i.e. of a shortest network interconnecting \(P\) which may contain vertices not in \(P\) --- called Steiner points. It is proved that, for \(1<p<\infty\), each Steiner point is of degree exactly three. Let \(L_ m(P)\) be the length of a minimal spanning tree and let the Steiner ratio be defined by \(\rho_ p=inf\{L_ s(P)/L_ m(P): P\subset L_ p\}\). It is shown that \(\rho_ \infty=2/3\) and \(\sqrt{\sqrt {2}/2\rho_ 1\rho_ 2}\leq \rho_ p\leq \sqrt{3}/2\) for any \(p\).
0 references
Steiner minimal trees
0 references
spanning trees
0 references
Steiner ratio
0 references
bounds
0 references
Steiner points
0 references