Minimum rectilinear Steiner tree of n points in the unit square

作者：Dumitrescu Adrian^*; Jiang Minghui

来源：Computational Geometry-Theory and Applications, 2018, 68: 253-261.

DOI：10.1016/j.comgeo.2017.06.007

• Minimum rectilinear Steiner tree
• Integer partition
• Packing
• Covering

Chung and Graham conjectured (in 1981) that n points in the unit square [0,1](2) can be connected by a rectilinear Steiner tree of length at most root n + 1. Here we confirm this conjecture for small values of n, and for some new infinite sequences of values of n (but not for all n). As an interesting byproduct we obtain close rational approximations of root n from below, for those n.

• 出版日期2018-3