On Steiner minimal trees withLp distance |
| |
Authors: | Zi -Cheng Liu and Ding -Zhu Du |
| |
Affiliation: | (1) Institute of Applied Mathematics, Academia Sinica, Beijing, People's Republic of China |
| |
Abstract: | LetLp be the plane with the distancedp(A1,A2) = (¦x1 –x2¦p + ¦y1 –y2¦p)/1p wherexi andyi are the cartesian coordinates of the pointAi. LetP be a finite set of points inLp. We consider Steiner minimal trees onP. It is proved that, for 1 <p < , each Steiner point is of degree exactly three. Define the Steiner ratio p to be inf{Ls(P)/Lm(P)¦PLp} whereLs(P) andLm(P) are lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. Hwang showed 1 = 2/3. Chung and Graham proved 2 > 0.842. We prove in this paper that {} = 2/3 and (2/2)12 p 3/2 for anyp.This work was supported in part by the National Science Foundation of China and the President Foundation of Academia Sinica. |
| |
Keywords: | Steiner trees Spanning trees Steiner ratio Lp distance Bounds |
本文献已被 SpringerLink 等数据库收录! |