Minimal Fillings of Finite Metric Spaces and Convex Polyhedra

2026/05/06 by A. O. Ivanov, A. A. Tuzhilin
Mathematics · #math.MG #math.OC #msc:51F99 #msc:90C35 #msc:90C08 #msc:49Q10 #msc:90C27

paper · pdf

arxiv created 2026/05/06 · arxiv updated 2026/07/31

Abstract

Problem of minimal parametric generalized fillings of finite metric space M (a version of optimal connection problem) leads to construction of a convex multidimensional polyhedra W_G for each tree G connecting M chosen as type of the parametric filling. The weight of the parametric minimal filling can be found as maximum on W_G of the special linear function corresponding to the distance vector of M. It is proved that the union of vertex sets of the polyhedra W_G over all possible G forms an extremal subset, i.e., coincides with the vertex set of its convex hull.

Citations

• Dual Linear Programming Problem and One-Dimensional Gromov Minimal Fillings of Finite Metric Spaces
• One-dimensional minimal fillings with negative edge weights

Related

• Dual Linear Programming Problem and One-Dimensional Gromov Minimal Fillings of Finite Metric Spaces
• One-dimensional minimal fillings with negative edge weights
• Beyond trees: the metric geometry of subsets of weighted Hamming cubes
• A Set of Questions in Combinatorial and Metric Geometry
• Two Applications of Point Matching