GROMOV MINIMAL FILLINGS FOR FINITE METRIC SPACES

Alexander O. Ivanov, Alexey A. Tuzhilin

Abstract: The problem discussed in this paper was stated by Alexander O. Ivanov and Alexey A. Tuzhilin in 2009. It stands at the intersection of the theories of Gromov minimal fillings and Steiner minimal trees. Thus, it can be considered as one-dimensional stratified version of Gromov minimal fillings problem. Here we state the problem; discuss various properties of one-dimensional minimal fillings, including a formula calculating their weights in terms of some special metrics characteristics of the metric spaces they join (it was obtained by A. Yu. Eremin after many fruitful discussions with participants of Ivanov–Tuzhilin seminar in Moscow State University); show various examples illustrating how one can apply the developed theory to get non-trivial results; discuss the connection with additive spaces appearing in bioinformatics and classical Steiner minimal trees having many applications, say, in transportation problem, chip design, evolution theory etc. In particular, we generalize the concept of Steiner ratio and get a few its modifications defined by means of minimal fillings, which could give a new approach to attack the long standing Gilbert–Pollack Conjecture on the Steiner ratio of the Euclidean plane.

Keywords: finite metric spaces, Gromov minimal fillings, Steiner minimal trees, extreme networks, Steiner ratio, additive spaces

Classification (MSC2000): 51F99; 51K99

Full text of the article: (for faster download, first choose a mirror)

• Compressed DVI file (36 kilobytes)
• Compressed PostScript file (420 kilobytes)
• PDF file (192 kilobytes)