Geodesic
Rectilinear spanning trees versus bounding boxes
The electronic journal of combinatorics, Tome 11 (2004) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

For a set $P\subseteq {\Bbb R}^2$ with $2\leq n=|P| < \infty$ we prove that ${{\rm mst}(P)\over{\rm bb}(P)} \leq{1\over\sqrt{2}}\sqrt{n}+{3\over2}$ where ${\rm mst}(P)$ is the minimum total length of a rectilinear spanning tree for $P$ and ${\rm bb}(P)$ is half the perimeter of the bounding box of $P$. Since the constant ${1\over\sqrt{2}}$ in the above bound is best-possible, this result settles a problem that was mentioned by Brenner and Vygen (Networks 38 (2001), 126-139).
DOI : 10.37236/1853
Classification : 05C05 
@article{10_37236_1853,
     author = {D. Rautenbach},
     title = {Rectilinear spanning trees versus bounding boxes},
     journal = {The electronic journal of combinatorics},
     year = {2004},
     volume = {11},
     number = {1},
     doi = {10.37236/1853},
     zbl = {1060.05023},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1853/}
}
TY  - JOUR
AU  - D. Rautenbach
TI  - Rectilinear spanning trees versus bounding boxes
JO  - The electronic journal of combinatorics
PY  - 2004
VL  - 11
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1853/
DO  - 10.37236/1853
ID  - 10_37236_1853
ER  - 
%0 Journal Article
%A D. Rautenbach
%T Rectilinear spanning trees versus bounding boxes
%J The electronic journal of combinatorics
%D 2004
%V 11
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1853/
%R 10.37236/1853
%F 10_37236_1853
D. Rautenbach. Rectilinear spanning trees versus bounding boxes. The electronic journal of combinatorics, Tome 11 (2004) no. 1. doi: 10.37236/1853

Cité par Sources :