首页 | 本学科首页   官方微博 | 高级检索  
     


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) = (¦x1x2¦p + ¦y1y2¦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 < infin, each Steiner point is of degree exactly three. Define the Steiner ratio rhovp to be inf{Ls(P)/Lm(P)¦PsubLp} whereLs(P) andLm(P) are lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. Hwang showed rhov1 = 2/3. Chung and Graham proved rhov2 > 0.842. We prove in this paper that rhov{infin} = 2/3 and radic(radic2/2)rhov1rhov2 le rhovp le radic3/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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号