Geodesic
Immersed polygons and their diagonal triangulations
Izvestiya. Mathematics , Tome 72 (2008) no. 1, pp. 63-90.

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

We introduce the notion of an ‘immersed polygon’, which naturally extends the notion of an ordinary planar polygon bounded by a closed (embedded) polygonal arc to the case when this arc may have self-intersections. We prove that every immersed polygon admits a diagonal triangulation and the closure of every embedded monotone polygonal arc bounds an immersed polygon. Given any non-degenerate planar linear tree, we construct an immersed polygon containing it. 
@article{IM2_2008_72_1_a3,
     author = {A. O. Ivanov and A. A. Tuzhilin},
     title = {Immersed polygons and their diagonal triangulations},
     journal = {Izvestiya. Mathematics },
     pages = {63--90},
     publisher = {mathdoc},
     volume = {72},
     number = {1},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2008_72_1_a3/}
}
TY  - JOUR
AU  - A. O. Ivanov
AU  - A. A. Tuzhilin
TI  - Immersed polygons and their diagonal triangulations
JO  - Izvestiya. Mathematics 
PY  - 2008
SP  - 63
EP  - 90
VL  - 72
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_2008_72_1_a3/
LA  - en
ID  - IM2_2008_72_1_a3
ER  - 
%0 Journal Article
%A A. O. Ivanov
%A A. A. Tuzhilin
%T Immersed polygons and their diagonal triangulations
%J Izvestiya. Mathematics 
%D 2008
%P 63-90
%V 72
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_2008_72_1_a3/
%G en
%F IM2_2008_72_1_a3
A. O. Ivanov; A. A. Tuzhilin. Immersed polygons and their diagonal triangulations. Izvestiya. Mathematics , Tome 72 (2008) no. 1, pp. 63-90. http://geodesic.mathdoc.fr/item/IM2_2008_72_1_a3/

[1] N. S. Gusev, “Kanonicheskoe razlozhenie kusochno-affinnykh funktsii, mnogogranniki-sledy i geometricheskie variatsionnye zadachi”, Fundam. i prikl. matematika, 12:1 (2006), 57–94 | MR

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

[3] P. Fermat, “Abhandlungen über Maxima und Minima”, Oswalds, Klassiker der Exakten Wissenschaften, 238, 1934 | Zbl

[4] M. R. Garey, R. L. Graham, D. S. Johnson, “Some $NP$-complete geometric problems”, Eighth annual ACM symposium on theory of computing (Hershey, 1976), Assoc. Comput. Mach., New York, 1976, 10–22 | MR | Zbl

[5] Z. A. Melzak, “On the problem of Steiner”, Canad. Math. Bull., 4 (1961), 143–148 | MR | Zbl

[6] F. K. Hwang, “A linear time algorithm for full Steiner trees”, Oper. Res. Lett., 4:5 (1986), 235–237 | DOI | MR | Zbl

[7] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich, Lektsii po teorii grafov, Nauka, M., 1990 ; O. Melnikov, R. Tyshkevich, V. Yemelichev, V. Sarvanov, Lectures on graph theory, Bibliographisches Institut, Mannheim, 1994 | MR | Zbl | MR | Zbl

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

[9] P. K. Prim, “Kratchaishie svyazyvayuschie seti i nekotorye obobscheniya”, Kiberneticheskii sbornik, No2, Nauka, M., 1961, 95–107; R. C. Prim, “Shortest connection networks and some generalizations”, Bell System Tech. J., 36 (1957), 1389–1401

[10] B. Delaunay, “Sur la sphère vide”, Bull. Acad. Sci. USSR. VII, 1934, no. 6, 793–800 | Zbl

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

[12] R. L. Graham, F. K. Hwang, “A remark on Steiner minimal trees”, Bull. Inst. Math. Acad. Sinica, 4:1 (1976), 177–182 | MR | Zbl

[13] F. R. K. Chung, F. K. Hwang, “A lower bound for the Steiner tree problem”, SIAM J. Appl. Math., 34:1 (1978), 27–36 | DOI | MR | Zbl

[14] D. Z. Du, F. K. Hwang, “A new bound for the Steiner ratio”, Trans. Amer. Math. Soc., 278:1 (1983), 137–148 | DOI | MR | Zbl

[15] F. R. K. Chung, R. L. Graham, “A new bound for Euclidean Steiner minimal trees”, Discrete geometry and convexity (New York, 1982), Ann. New York Acad. Sci., 440, New York Acad. Sci., New York, 1985, 328–346 | DOI | MR | Zbl

[16] D. Z. Du, F. K. Hwang, “An approach for proving lower bounds: solution of Gilbert–Pollak's conjecture on steiner ratio”, 31st annual symposium on foundations of computer science, Vol. I, II (St. Louis, MO, 1990), IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 76–85 | MR

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

[18] E. B. Vinberg, Kurs algebry, Faktorial Press, M., 2002; E. B. Vinberg, A course in algebra, Grad. Stud. Math., 56, Amer. Math. Soc., Providence, RI, 2003 | MR | Zbl