MINIMUM STEINER TREES IN NORMED PLANES

CSpace

	MINIMUM STEINER TREES IN NORMED PLANES
	DU, DZ ; GAO, B ; GRAHAM, RL ; LIU, ZC ; WAN, PJ
	1993
发表期刊	DISCRETE & COMPUTATIONAL GEOMETRY
ISSN	0179-5376
卷号	9 期号:4 页码:351-370
摘要	A minimum Steiner tree for a given set X of points is a network interconnecting the points of X having minimum possible total length. In this note we investigate various properties of minimum Steiner trees in normed planes, i.e., where the ''unit disk'' is an arbitrary compact convex centrally symmetric domain D having nonempty interior. We show that if the boundary of D is strictly convex and differentiable, then each edge of a full minimum Steiner tree is in one of three fixed directions. We also investigate the Steiner ratio rho(D) for D, and show that, for any D, 0.623 < rho(D) < 0.8686.
语种	英语
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Theory & Methods ; Mathematics
WOS记录号	WOS:A1993LD07300002
出版者	SPRINGER VERLAG
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/27962
专题	中国科学院数学与系统科学研究院
通讯作者	DU, DZ
作者单位	1.CHINESE ACAD SCI,INST APPL MATH,BEIJING,PEOPLES R CHINA 2.AT&T BELL LABS,MURRAY HILL,NJ 07974 3.PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08544 4.RUTGERS UNIV,CTR DISCRETE MATH & THEORET COMP SCI,NEW BRUNSWICK,NJ 08903
推荐引用方式 GB/T 7714	DU, DZ,GAO, B,GRAHAM, RL,et al. MINIMUM STEINER TREES IN NORMED PLANES[J]. DISCRETE & COMPUTATIONAL GEOMETRY,1993,9(4):351-370.
APA	DU, DZ,GAO, B,GRAHAM, RL,LIU, ZC,&WAN, PJ.(1993).MINIMUM STEINER TREES IN NORMED PLANES.DISCRETE & COMPUTATIONAL GEOMETRY,9(4),351-370.
MLA	DU, DZ,et al."MINIMUM STEINER TREES IN NORMED PLANES".DISCRETE & COMPUTATIONAL GEOMETRY 9.4(1993):351-370.