Geodesic
The geometry of inner spanning trees for planar polygons
Izvestiya. Mathematics , Tome 76 (2012) no. 2, pp. 215-244.

Voir la notice de l'article provenant de la source Math-Net.Ru

We study the geometry of minimal inner spanning trees for planar polygons (that is, spanning trees whose edge-intervals lie in these polygons). We construct analogues of Voronoi diagrams and Delaunay triangulations, prove that every minimal inner spanning tree is a subgraph of an appropriate Delaunay triangulation, and describe the possible structure of the cells of such triangulations.
Keywords: inner spanning tree, planar polygon, Euclidean spanning tree, Voronoi diagram, Steiner ratio, characteristic domain.
Mots-clés : Delaunay triangulation 
@article{IM2_2012_76_2_a0,
     author = {A. O. Ivanov and A. A. Tuzhilin},
     title = {The geometry of inner spanning trees for planar polygons},
     journal = {Izvestiya. Mathematics },
     pages = {215--244},
     publisher = {mathdoc},
     volume = {76},
     number = {2},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2012_76_2_a0/}
}
TY  - JOUR
AU  - A. O. Ivanov
AU  - A. A. Tuzhilin
TI  - The geometry of inner spanning trees for planar polygons
JO  - Izvestiya. Mathematics 
PY  - 2012
SP  - 215
EP  - 244
VL  - 76
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_2012_76_2_a0/
LA  - en
ID  - IM2_2012_76_2_a0
ER  - 
%0 Journal Article
%A A. O. Ivanov
%A A. A. Tuzhilin
%T The geometry of inner spanning trees for planar polygons
%J Izvestiya. Mathematics 
%D 2012
%P 215-244
%V 76
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_2012_76_2_a0/
%G en
%F IM2_2012_76_2_a0
A. O. Ivanov; A. A. Tuzhilin. The geometry of inner spanning trees for planar polygons. Izvestiya. Mathematics , Tome 76 (2012) no. 2, pp. 215-244. http://geodesic.mathdoc.fr/item/IM2_2012_76_2_a0/

[1] F. P. Preparata, M. I. Shamos, Computational geometry. An introduction, Texts Monogr. Comput. Sci., Springer–Verlag, New York, 1985 | MR | MR | Zbl | Zbl

[2] A. O. Ivanov, A. A. Tuzhilin, Teoriya ekstremalnykh setei, In-t kompyuternykh issledovanii, M.–Izhevsk, 2003

[3] A. O. Ivanov, A. A. Tuzhilin, Branching solutions to one-dimensional variational problems, World Scientific, River Edge, NJ, 2001 | MR | Zbl

[4] J. B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem”, Proc. Amer. Math. Soc., 7 (1956), 48–50 | DOI | MR | Zbl

[5] R. C. Prim, “Shortest connecting networks and some generalizations”, Bell System Tech. J., 36 (1957), 1389–1401

[6] O. Melnikov, R. I. Tyshkevich, V. A. Yemelichev, V. I. Sarvanov, Lectures on graph theory, Wissenschaftsverlag, Mannheim, 1994 | MR | MR | Zbl | Zbl

[7] M. I. Shamos, Computational geometry, Ph. D. Thesis, Yale University, 1978

[8] B. N. Delone, “O pustom share”, Izv. AN SSSR, 6 (1934), 793–800 | Zbl

[9] A. V. Skvortsov, Triangulyatsiya Delone i ee primenenie, Izd-vo Tomskogo un-ta, Tomsk, 2002

[10] G. Voronoi, “Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs”, J. Reine Angew. Math., 134 (1908), 198–287 | DOI | Zbl

[11] A. O. Ivanov, A. A. Tuzhilin, “Immersed polygons and their diagonal triangulations”, Izv. Math., 72:1 (2008), 63–90 | DOI | MR | Zbl

[12] E. N. Gilbert, H. O. Pollak, “Steiner minimal trees”, SIAM J. Appl. Math., 16:1 (1968), 1–29 | DOI | MR | Zbl

[13] D.-Z. Du, F. K. Hwang, “A proof of the Gilbert–Pollak conjecture on the Steiner ratio”, Algorithmica, 7:2–3 (1992), 121–135 | DOI | MR | Zbl

[14] A. O. Ivanov, A. A. Tuzhilin, “Otnoshenie Shteinera: sovremennoe sostoyanie”, Matem. voprosy kibern., 11 (2002), 27–48 | MR | Zbl

[15] P. de Wet, “The Euclidean Steiner ratio: some recent results”, Proceedings of the 5th Asian mathematical conference (Kuala Lumpur, Malaysia, 2009), Universiti Sains Malaysia, Penang, 2009, 442–446 | Zbl

[16] N. Innami, B. H. Kim, Y. Mashiko, K. Shiohama, “The Steiner ratio conjecture of Gilbert–Pollak may still be open”, Algorithmica, 57:4 (2010), 869–872 | DOI | MR | Zbl

[17] D. Burago, Yu. Burago, S. Ivanov, A course in metric geometry, Grad. Stud. Math., 33, Amer. Math. Soc., Providence, RI, 2001 | MR | Zbl

[18] H. Busemann, The geometry of geodesics, Academic Press, New York, 1955 | MR | MR | Zbl | Zbl