Abstract: The classical Steiner problem is a problem of finding the shortest connected graphs (networks) whose vertex sets contain a given set of points in the Euclidean plane. It is known that the Euclidean Steiner problem is NP-hard, i.e. it is not known whether an optimal solution can be found by using a polynomial-time algorithm. Therefore, to construct an appropriate and fast algorithm for finding a shortest network one should describe restrictions on possible structures of shortest networks. It is evident that a shortest network has to be local minimal (a neighborhood of each point is shortest with respect to some canonical set of points) and extremal (the length of the network does not increase under deformations). In the case of Riemann manifolds and smooth normed planes these two notions coincide, but they differ in the case of non-smooth normed planes. We discuss the Steiner problem in non-smooth normed planes. We show a connection between local minimal and extremal networks, and give formulas for finding the length of an extremal network.

This talk will be accessible to undergraduates.