Minimum steiner trees in normed planes |
| |
Authors: | Ding-Zhu Du Biao Gao Ronald L Graham Zi-Cheng Liu Peng-Jun Wan |
| |
Institution: | (1) Computer Science Department, University of Minnesota, 55455 Minneapolis, MN, USA;(2) Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing, People's Republic of China;(3) AT&T Bell Laboratories, 07974 Murray Hill, NJ, USA;(4) Computer Science Department, Princeton University, 08544 Princeton, NJ, USA |
| |
Abstract: | A minimum Steiner tree for a given setX of points is a network interconnecting the points ofX 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 domainD having nonempty interior. We show that if the boundary ofD 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(D) forD, and show that, for anyD, 0.623<(D)<0.8686.Part of this work was done while Ding-Zhu Du was at the Computer Science Department, Princeton University and the Center for Discrete Mathematics and Theoretical Computer Science at Rutgers. Supported by NSF under Grant STC88-09648. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|