×
Caffarelli, Elena A.; Halverson, Denise M.; Jensen, Ryan J.

The Steiner problem on surfaces of revolution. (English) Zbl 1305.51005

Graphs Comb. 30, No. 2, 315-342 (2014).
The Steiner problem consists on finding the shortest path network connecting a finite set of given points on a surface. It is well understood in the Euclidean plane and on surfaces of constant curvature. The aim of the paper is to develop an algorithm for the \(n\)-point Steiner problem on a surface of revolution with a non-decreasing generating function. Extra complexities include for this problem describing the length-minimizing geodesics and the large number of combinations of points that could lead to a minimizing configuration.
The points in the surface are first projected to the weighted plane with coordinates \((u,v)\) and metric \(\lambda(v)^2du^2+dv^2\). Then geodesics are determined in Section 4 in the cases where \(\lambda\) is constant or piecewise constant (using that the geodesic is a straight segment or a polygonal) or continuous using Clairaut’s relation. The choice of a minimal geodesic is discussed in Section 5, and applications to the \(3\)-point Steiner problem are given in Section 6, where only three cases are shown to be possible in Proposition 6.4. In Section 7, an extension of the algorithm to the \(n\)-point Steiner problem is discussed.
Reviewer: Manuel Ritoré (Granada)

MSC:

51E10 Steiner systems in finite geometry
49Q10 Optimization of shapes other than minimal surfaces

Keywords:

Steiner problem; surface of revolution; non-planar surface; weighted plane
PDF BibTeX XML Cite
\textit{E. A. Caffarelli} et al., Graphs Comb. 30, No. 2, 315--342 (2014; Zbl 1305.51005)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Brazil, M., Rubinstein, J.H., Thomas, D.A., Weng, J.F., Wormald, N.C.: Shortest networks on spheres, Network design: connectivity and facilities location (Princeton, NJ, 1997). In: DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 40, pp. 453-461. American Mathematical Society, Providence (1998) · Zbl 0915.05043
[2] do Carmo, M.P.: Differential geometry of curves and surfaces, Prentice-Hall Inc., Englewood Cliffs, N.J. (1976) (Translated from the Portuguese.) · Zbl 0326.53001
[3] Garey, M.R.; Graham, R.L.; Johnson, D.S., The complexity of computing Steiner minimal trees, SIAM J. Appl. Math., 32, 835-859, (1977) · Zbl 0399.05023
[4] Giambattista, A., Richardson, B.M., Richardson, R.C.: Physics. McGraw Hill, Boston (2008) · Zbl 0884.05036
[5] Gilbert, E.N.; Pollak, H.O., Steiner minimal trees, SIAM J. Appl. Math., 16, 1-29, (1968) · Zbl 0159.22001
[6] Gordeev, È.N.; Tarastsov, O.G., The Steiner problem, A Survey. Diskret. Mat., 5, 3-28, (1993) · Zbl 0805.05018
[7] Hwang, F.K.; Weng, J.F., Hexagonal coordinate systems and Steiner minimal trees, Discret. Math., 62, 49-57, (1986) · Zbl 0601.05016
[8] Hwang, F.K., Richards, D.S., Winter, P.: The Steiner tree problem. In: Annals of Discrete Mathematics, vol. 53. North-Holland Publishing Co., Amsterdam (1992) · Zbl 0774.05001
[9] Jiang, X.Y., The Steiner problem on a surface, Appl. Math. Mech, 8, 911-916, (1987) · Zbl 0646.45007
[10] Kreyszig, E.: Differential geometry , Mathematical Expositions, No. 11. University of Toronto Press, Toronto (1959) · Zbl 0088.13901
[11] Lee, A., Lytle, J., Halverson, D., Sampson, D.: The Steiner problem on narrow and wide cones. Thesis Project, Brigham Young University (in press) · Zbl 0601.05016
[12] Litwhiler, D.W.; Aly, A.A., Steiner’s problem and fagnano’s result on the sphere, Math. Program., 18, 286-290, (1980) · Zbl 0433.90029
[13] March, D., Halverson, D.: Steiner tree constructions in hyperbolic space. Thesis Project, Brigham Young University · Zbl 0808.51022
[14] Melzak, Z.A., On the problem of Steiner, Can. Math. Bull., 4, 143-148, (1961) · Zbl 0101.13201
[15] Montiel, S., Ros, A.: Curves and surfaces, 2nd edn. In: Graduate Studies in Mathematics, vol. 69. American Mathematical Society, Providence (2009) (Translated from the 1998 Spanish original by Montiel and edited by Donald Babbitt.) · Zbl 0884.05036
[16] Oprea, J.: Differential geometry and its applications, 2nd edn. In: Classroom Resource Materials Series. Mathematical Association of America, Washington, DC (2007) · Zbl 1153.53001
[17] Scott Provan, J., An approximation scheme for finding Steiner trees with obstacles, SIAM J. Comput., 17, 920-934, (1988) · Zbl 0665.68053
[18] Rubinstein, J.H.; Thomas, D.A., A variational approach to the Steiner network problem, ann, Oper. Res., 33, 481-499, (1991) · Zbl 0734.05040
[19] Weng, J.F., Shortest networks for smooth curves, SIAM J. Optim., 7, 1054-1068, (1997) · Zbl 0884.05036
[20] Weng, J.F., Steiner trees on curved surfaces, Graphs Combin., 17, 353-363, (2001) · Zbl 0982.05036
[21] Weng, J.F., Steiner polygons in the Steiner problem, Geom. Dedicata, 52, 119-127, (1994) · Zbl 0808.51022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.