The geometry of plane locally minimal binary trees

A. O. Ivanov

Sbornik. Mathematics, Tome 186 (1995) no. 9, pp. 1271-1301

Résumé

An effective bound is obtained for the possible topology of a plane locally minimal binary tree in terms of its rotation number and the geometry of the boundary set.

Bibliographie

[1] Clark R. C., “Communication networks, soap films and vectors”, Phys. Ed., 16 (1981), 32–37 | DOI

[2] Cockayne E. J., “On the Steiner problem”, Canad. J. Math., 10 (1967), 431–450 | MR | Zbl

[3] Dijkstra E. W., “A note on two problems with connection with graphs”, Numer. Math., 1:5 (1959), 269–271 | DOI | MR | Zbl

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

[5] Du D. Z., Hwang F. K., A Proof of Gilbert–Pollak's Conjecture on the Steiner Ratio, DIMACS Technical Report No 90–72, 1990

[6] Du D. Z., Hwang F. K., “An approach for proving lower bounds: solution of Gilbert–Pollak's Conjecture on the Steiner Ratio”, Proc. of the 31st annual symp. on found. of comp. science, 1990

[7] Du D. Z., Hwang F. K., Chao S. C., “Steiner minimal trees for points on a circle”, Proc. Amer. Math. Soc., 95:4 (1985), 613–618 | DOI | MR | Zbl

[8] Du D. Z., Hwang F. K., Song G. D., Ting G. T., “Steiner minimal trees on sets of four points”, Discr. and Comp. Geometry, 2 (1987), 401–414 | DOI | MR | Zbl

[9] Du D. Z., Hwang F. K., Weng J. F., “Steiner minimal trees for points on a zig-zag lines”, Trans. Amer. Math. Soc., 278:1 (1983), 149–156 | DOI | MR | Zbl

[10] Du D. Z., Hwang F. K., Weng J. F., “Steiner minimal trees for Regular Polygons”, Disc. and Comp. Geometry, 2 (1987), 65–84 | DOI | MR | Zbl

[11] Du D. Z., Hwang F. K., Yao E. N., “The Steiner ratio conjecture is true for five points”, J. Combin Thy. Ser. A38, 1985, 230–240 | MR | Zbl

[12] Fomenko A. T., Tuzhilin A. A., Elements of geometry and topology of minimal surfaces in three-dimensional space, Translations of Mathematical Monographs, 93, AMS, 1992 | MR

[13] Garey M. R., Graham R. L., Johnson D. S., “Some $NP$-complete geometric problems”, Eighth Annual Symp. on Theory of Comput., 1976, 10–22 | MR | Zbl

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

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

[16] Hwang F. K., Weng J. F., “Hexagonal coordinate Systems and Steiner minimal trees”, Disc. Math., 62 (1986), 49–57 | DOI | MR | Zbl

[17] Hwang F. K., Richards D., Winter P., The Steiners Tree Problem, Elsevier Science Publishers (to appear) | MR

[18] Ivanov A. O., Iskhakov I. V., Tuzhilin A. A., “Minimalnye seti na pravilnykh mnogougolnikakh: realizatsiya lineinykh parketov”, Vestnik MGU, 1993 (to appear)

[19] Ivanov A. O., Tuzhilin A. A., “Reshenie zadachi Shteinera dlya vypuklykh granits”, UMN, 45:2 (1990), 207–208 | MR | Zbl

[20] Ivanov A. O., Tuzhilin A. A., “Zadacha Shteinera dlya vypuklykh granits ili ploskie minimalnye seti”, Matem. sb., 182:12 (1991), 1813–1844 | MR

[21] Ivanov A. O., Tuzhilin A. A., “Geometriya minimalnykh setei i odnomernaya problema Plato”, UMN, 47:2 (1992), 53–115 | MR | Zbl

[22] Ivanov A. O., Tuzhilin A. A., “The Steiner problem for convex boundaries. 1: the general case”, Advances in Soviet Mathematics, 15, AMS, 1993, 15–92 | MR

[23] Ivanov A. O., Tuzhilin A. A., “The Steiner problem for convex boundaries. 2: the regular case”, Advances in Soviet Mathematics, 15, AMS, 1993, 93–131 | MR

[24] Ivanov A. O., Ptitsyna I. V., Tuzhilin A. A., “Klassifikatsiya zamknutykh minimalnykh setei na ploskikh dvumernykh torakh”, Matem. sb., 183:12 (1992), 3–44 | MR | Zbl

[25] Ivanov A. O., Tuzhilin A. A., Minimal Networks. Steiner Problem and Its Generalizations, CRC Press, 1994 | MR | Zbl

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

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

[28] Pollak H. O., “Some remarks on the Steiner problem”, J. Combin. Thy. Ser. A24, 1978, 278–295 | DOI | MR | Zbl

[29] Preparata F., Shamos M., Computational Geometry. An introduction, Springer-Verlag, New York, 1985 | MR

[30] Prim R. C., “Shortest connecting networks and some generalizations”, BSTJ, 36 (1957), 1389–1401

[31] Rubinstein J. H., Thomas D. A., “The Steiner ratio conjecture for six points”, J. Combin. Thy. Ser. A58, 1989, 54–77 | MR

[32] Shamos M. I., Computational Geometry, Ph. D. Thesis, Dept. of Comput. Sci., Yale Univ., 1978 | Zbl

[33] Smith W. D., “How to find Steiner minimal tries in Euclidean $d$-space”, Algoritmica (to appear)

[34] Edmonds A. L., Ewing J. H., Kulkarni R. S., “Regular tesselations of surfaces and $(p,q,2)$-triangle groups”, Ann. Math., 116 (1982), 113–132 | DOI | MR | Zbl

[35] Edmonds A. L., Ewing J. H., Kulkarni R. S., “Torsion free subgroups of Fuchian groups and tesselations of surfaces”, Inv. Math., 69 (1982), 331–346 | DOI | MR | Zbl

[36] Shklyanko I. V., “The one dimensional Plateau problem on surfaces”, Vestnik Moskov. Univ. Ser. Mat., 1989, no. 3, 8–11 | MR | Zbl

[37] Dao Chong Tkhi, Fomenko A. T., Minimalnye poverkhnosti i problema Plato, Nauka, M., 1987 | MR | Zbl

[38] Fomenko A. T., Topologicheskie variatsionnye zadachi, Izd-vo MGU, M., 1984 | MR | Zbl

[39] Zacharias M., Encyklopädie der Mathematischen Wissenschaften, V. 3 AB9

[40] Kuhn H. W., “Steiner's problem revisted”, Studies in Optimization, Studies in Math., 10, eds. Dantzig G. B., Eaves B. C., Math. Assoc. Amer., 1975, 53–70

[41] Jarnik V., Kössler M., “O minimalnich grafeth obeahujicich n danijch bodu”, Cas. Pest. Mat. a Fys., 63 (1934), 223–235 | Zbl