Tropical Fermat–Weber Polytropes
Open Access
- 28 July 2026
- journal article
- research article
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 76 (4) , 2220-2242
Abstract
We study the geometry of tropical Fermat–Weber points, that is, optimal solutions to a location problem over a projective space using a dissimilarity measure derived from the tropical metric. It is well-known that for a given sample, such points are not necessarily unique, and we show that the set of all possible Fermat–Weber points forms a polytrope. This follows from the fact that our location problem turns out to be dual to a particular minimum-cost flow problem, and we describe the polytrope of optimal locations in the terminology of tropical geometry. We also provide a simple gradient descent algorithm that converges to the Fermat–Weber polytrope.Keywords
All Related Versions
Funding Information
- NSF (DMS 2409819)
- NSF (DMS-1929348)
- Japan Society for the Promotion of Science London (JP22K19816, JP22H02364 and JP25K15283)
This publication has 23 references indexed in Scilit:
- Tropical gradient descentJournal of Global Optimization, 2025
- Tropical convexity in location problemsMathematical Methods of Operations Research, 2024
- Tropical Logistic Regression Model on Space of Phylogenetic TreesBulletin of Mathematical Biology, 2024
- Tropical medians by transportationMathematical Programming, 2023
- Tropical hyperplane arrangements and oriented matroidsMathematische Zeitschrift, 2008
- Combinatorics of hypergeometric functions associated with positive roots1997
- The Fermat—Weber location problem revisitedMathematical Programming, 1995
- An implementation of an algorithm for univariate minimization and an application to nested optimizationMathematical Programming, 1988
- A strongly polynomial minimum cost circulation algorithmCombinatorica, 1985
- Six theorems about injective metric spacesCommentarii Mathematici Helvetici, 1964