Two probabilistic results on rectilinear steiner trees |
| |
Authors: | Marshall W. Bern |
| |
Affiliation: | 1. Computer Science Division, University of California, 94720, Berkeley, CA, USA
|
| |
Abstract: | In recent years, researchers have proven many theorems of the following form: given points distributed according to a Poisson process with intensity parameterN on the unit square, the length of the shortest spanning tree (rectilinear Steiner tree, traveling salesman tour, or some other functional) on these points is, with probability one, asymptotic to β√N for some constant β (which is presumably different for different functionals). Though these theorems are well understood, very little is known about the constants β. In this paper we prove that the constants in the cases of rectilinear spanning tree and rectilinear Steiner tree do, indeed, differ. This proof is constructive in the sense that we give a polynomial-time heuristic algorithm that produces a Steiner tree of expected length some fraction shorter than a minimum spanning tree. We continue the analysis to prove a second result: the expected value of the minimum number of Steiner points in a shortest rectilinear Steiner tree grows linearly withN. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|