This website uses features that are not well-supported by your browser. Please consider upgrading to a browser and version that fully supports CSS Grid and the CSS Flexible Box Layout Module.
Sidebar image
NB: A PDF version of this announcement (suitable for posting) is also available.

Steiner problem in normed planes

Denis Ilyutko
Lomonosov Moscow State University

Thursday, April 14, 2011
007 Kemeny Hall, 4 pm
Tea 3:30 pm, 300 Kemeny Hall

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.