REDUCING THE STEINER PROBLEM IN A NORMED SPACE

CSpace

	REDUCING THE STEINER PROBLEM IN A NORMED SPACE
	DU, DZ ; HWANG, FK
	1992-12-01
发表期刊	SIAM JOURNAL ON COMPUTING
ISSN	0097-5397
卷号	21 期号:6 页码:1001-1007
摘要	Consider a set P of points in a normed space whose unit sphere is a d-dimensional symmetric polytope with 2d extreme points. This paper proves that there always exists a Steiner minimum tree whose Steiner points are located only at points whose coordinates appear in points of P. This generalizes a recent result of Snyder on d-dimensional rectilinear space, which itself extends Hanan's well-known and much quoted result on the rectilinear plane. Furthermore, the proof in this paper is much simpler than Snyder's proof, even considerably shorter than Hanan's proof. A consequence of this result is that the Steiner problem for P in such a space is reduced to a Steiner problem on graphs and is solvable by any existing Steiner graph algorithms. The paper also conjectures that such a reduction is impossible if he polytope has more than 2d extreme points and provides partial support for the conjecture.
关键词	STEINER TREE MINKOWSKI SPACE NORMED SPACE
语种	英语
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Theory & Methods ; Mathematics, Applied
WOS记录号	WOS:A1992KB48300001
出版者	SIAM PUBLICATIONS
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/28521
专题	中国科学院数学与系统科学研究院
通讯作者	DU, DZ
作者单位	1.CHINESE ACAD SCI,INST APPL MATH,BEIJING,PEOPLES R CHINA 2.AT&T BELL LABS,MURRAY HILL,NJ 07974
推荐引用方式 GB/T 7714	DU, DZ,HWANG, FK. REDUCING THE STEINER PROBLEM IN A NORMED SPACE[J]. SIAM JOURNAL ON COMPUTING,1992,21(6):1001-1007.
APA	DU, DZ,&HWANG, FK.(1992).REDUCING THE STEINER PROBLEM IN A NORMED SPACE.SIAM JOURNAL ON COMPUTING,21(6),1001-1007.
MLA	DU, DZ,et al."REDUCING THE STEINER PROBLEM IN A NORMED SPACE".SIAM JOURNAL ON COMPUTING 21.6(1992):1001-1007.