Branching geodesics in normed spaces

A. O. Ivanov ; A. A. Tuzhilin

Izvestiya. Mathematics , Tome 66 (2002) no. 5, pp. 905-948.

Résumé

We study branching extremals of length functionals on normed spaces. This is a natural generalization of the Steiner problem in normed spaces. We obtain criteria for a network to be extremal under deformations that preserve the topology of networks as well as under deformations with splitting. We discuss the connection between locally shortest networks and extremal networks. In the important particular case of the Manhattan plane, we get a criterion for a locally shortest network to be extremal.

Bibliographie

[1] 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

[2] Francis R. L., “A note on the optimum location of new machines in existing plant layouts”, J. Indust. Engrg., 14 (1963), 57–59

[3] Garey M. R., Johnson D. S., “The Rectilinear Steiner Problem is $NP$-Complete”, SIAM J. Appl. Math., 32 (1977), 826–834 | DOI | MR | Zbl

[4] Hanan M., “On Steiner's Problem with Rectilinear Distance”, SIAM J. Appl. Math., 14 (1966), 255–265 | DOI | MR | Zbl

[5] Hwang F. K., “On Steiner minimal trees with rectilinear distance”, SIAM J. of Appl. Math., 30 (1976), 104–114 | DOI | MR | Zbl

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

[7] Ivanov A. O., “Geometriya ploskikh lokalno minimalnykh binarnykh derevev”, Matem. sb., 186:9 (1995), 45–76 | MR | Zbl

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

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

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

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

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

[13] Ivanov A. O., Tuzhilin A. A., “Klassifikatsiya minimalnykh skeletov s pravilnoi granitsei”, UMN, 51:4 (1996), 157–158 | MR | Zbl

[14] Ivanov A. O., Tuzhilin A. A., “Geometriya mnozhestva minimalnykh setei s zadannoi topologiei i fiksirovannoi granitsei”, Izv. RAN. Ser. matem., 61:6 (1997), 119–152 | MR | Zbl

[15] Ivanov A. O., Tuzhilin A. A., Razvetvlennye geodezicheskie. Geometricheskaya teoriya lokalno minimalnykh setei, The Edwin Mellen Press, Lewiston–Queenston, 1999

[16] Ivanov A. O., Tuzhilin A. A., Branching solutions to one-dimensional bariational problems, World Scientific Pub. Press, Singapore, 2001 | MR

[17] Ivanov A. O., Khong Van Le, Tuzhilin A. A., “Osobennosti lagranzhianov i kriterii kritichnosti”, Matem. zametki, 69:4 (2001), 566–580 | MR | Zbl

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

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

[20] Mikhalevich V. S., Trubin V. A., Shor N. Z., Optimizatsionnye zadachi v industrialnom planirovanii: modeli, metody, algoritmy, Nauka, M., 1986 | MR

[21] Ptitsyna I. V., “Klassifikatsiya zamknutykh lokalno minimalnykh setei na ploskikh butylkakh Kleina”, Vestn. MGU. Ser. matem., 1995, no. 2, 15–22 | MR | Zbl

[22] Richards D. S., Salowe J. S., “A Linear–Time Algorithm To Constract a Rectilinear Steiner Minimal Tree for $k$-Extremal Point Sets”, Algorithmica, 7 (1992), 247–276 | DOI | MR | Zbl

[23] Tuzhilin A. A., “Polnaya klassifikatsiya lokalno minimalnykh binarnykh derevev s pravilnoi granitsei. Sluchai skeletov”, Fundamentalnaya i prikladnaya matematika, 2:2 (1996), 511–562 | MR | Zbl