pith. sign in

arxiv: 2402.14287 · v5 · submitted 2024-02-22 · 🧮 math.CO

Tropical Fermat-Weber Polytropes

John Sabol , David Barnhill , Ruriko Yoshida , Keiji Miura This is my paper

Pith reviewed 2026-05-24 04:07 UTC · model grok-4.3

classification 🧮 math.CO
keywords tropical geometryFermat-Weber pointspolytropesminimum-cost flowlocation problemtropical metricprojective spacegradient descent
0
0 comments X

The pith

The set of all Fermat-Weber points under the tropical metric forms a polytrope for any finite sample.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that solutions to a location problem in tropical projective space need not be unique, yet the full collection of optimal points always forms a polytrope. A reader would care because the result replaces the search for a single best location with an explicit geometric object that contains every best location. The argument proceeds by establishing a duality between the location problem and a minimum-cost flow problem, so that the optimal flows directly parametrize the desired set. The authors also supply a gradient descent procedure that converges to the entire polytrope rather than to one of its points.

Core claim

For any finite collection of points equipped with the tropical metric, the Fermat-Weber set is a polytrope; this holds because the location problem is dual to a minimum-cost flow problem whose optimal solutions exactly parametrize all Fermat-Weber points, and the polytrope can therefore be described in the language of tropical geometry.

What carries the argument

Duality of the tropical location problem to a minimum-cost flow problem, whose optimal flows give the Fermat-Weber set as a polytrope.

If this is right

  • The polytrope admits a direct description in tropical geometry.
  • A gradient descent algorithm converges to the full Fermat-Weber polytrope.
  • Every optimal location corresponds to an optimal flow in the dual minimum-cost flow problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Solving one minimum-cost flow instance yields the complete set of optimal locations rather than a single point.
  • The same duality technique may apply to location problems that use other tropical dissimilarity measures.
  • The polytrope supplies a natural object for quantifying the range of equally good locations in data-analysis settings.

Load-bearing premise

The location problem is dual to a particular minimum-cost flow problem whose optimal solutions exactly parametrize the Fermat-Weber set.

What would settle it

A concrete finite sample of points in tropical projective space whose Fermat-Weber set is not a polytrope or for which the stated duality to the minimum-cost flow problem fails.

Figures

Figures reproduced from arXiv: 2402.14287 by David Barnhill, John Sabol, Keiji Miura, Ruriko Yoshida.

Figure 1
Figure 1. Figure 1: Left: Tropical ball, Br(u) ∈ R 3/R1 with radius r. Center point is indicated by “+” and the minimum generating set V ′ are shown as black closed circles. Pseudo-vertices not part of V ′ are shown as open circles. Right: The max-plus (solid) and min-plus (dashed) tropical hyperplanes with apex at u, along with Br(u) (dotted). Note the correspondence between the rays of the min-plus hyperplane and the genera… view at source ↗
Figure 2
Figure 2. Figure 2: Left: Tuples defining the type for each face of the hyperplane arrangement given by S in Example 1. Not shown are types for the 0-dimensional faces p1, p2, and (0, 1, 1) (the intersection of hyperplanes), but they can be easily inferred. For instance, the point (0,1,1) has type (23, 13). Right: Covectors corresponding to the cells of CovDec(V ), where ∗ denotes the empty set. Covectors for 0-dimensional ce… view at source ↗
Figure 3
Figure 3. Figure 3: Left: CovDec(S) with the unique bounded cell C. Center: The bipartite graph Kn,d (dotted arcs) overlaid by its subgraph GC (solid arcs), the covector graph of cell C. GC encodes the combinatorial structure of the hyperplane arrangement T (S), which is equivalently represented by the fine-type matrix T shown below the graph. The dual coarse-type #t = (1, 1, 1) is equal to the coarse-type #τ in this instance… view at source ↗
Figure 4
Figure 4. Figure 4: The bi-tropical covector decomposition BCD( [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The minimum cost flow setup for (D1) given four points in [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Left: The residual network G˜(π ∗ , ϕ∗ ) for Example 3 created by reversing arc directions/costs for arcs such that π ∗ = 1, ϕ∗ = 1. Pairwise shortest paths in G˜ yield the Kleene star, shown on the bottom left. Right: Half-sectors for each point intersect on the shaded region, which corresponds to FW(V ). Rays corresponding to the max-hyperplane portion of the half-sectors are drawn solid while min-hyperp… view at source ↗
Figure 7
Figure 7. Figure 7: A portion of BCD(V ) from Example 3. Per (10), we can equivalently calculate covectors by considering the arrangement of min/max-plus tropical hyperplanes with apices at y. Given our usual convention of drawing max-plus hyperplanes solid and min-plus hyperplanes dashed, we do the reverse at y to remind the reader we have “swapped” perspectives. The gradient at y and elements of the subdifferential evaluate… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper studies the geometry of tropical Fermat-Weber points, i.e., optimal solutions to a location problem in projective space under a dissimilarity derived from the tropical metric. It claims that for a given sample the set of all such points forms a polytrope; this follows from a duality between the location problem and a particular minimum-cost flow problem whose optimal solutions parametrize the Fermat-Weber set. The authors describe the resulting polytrope in tropical-geometric terms and supply a gradient-descent algorithm that converges to it.

Significance. If the duality is rigorously established and the parametrization of optima is exact, the result supplies a concrete geometric object (a polytrope) for a non-unique tropical location problem and links it to min-cost flow, which is a standard combinatorial object. The algorithmic contribution is a practical bonus. These features would be of interest to researchers working at the intersection of tropical geometry and discrete optimization.

major comments (1)
  1. [Abstract, paragraph 3] Abstract (paragraph 3) and the corresponding section deriving the duality: the central claim that the Fermat-Weber set is a polytrope rests on the assertion that the location problem is dual to a min-cost flow problem whose optimal solutions exactly parametrize the set. No derivation steps, preservation argument, or verification that the chosen tropical dissimilarity measure yields an exact correspondence are supplied in the abstract; if this duality fails to be bijective on the optima, the polytrope conclusion does not follow.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thoughtful review and for highlighting the need for clearer exposition of the duality. We address the concern below and will revise the manuscript to strengthen the presentation.

read point-by-point responses

  1. Referee: [Abstract, paragraph 3] Abstract (paragraph 3) and the corresponding section deriving the duality: the central claim that the Fermat-Weber set is a polytrope rests on the assertion that the location problem is dual to a min-cost flow problem whose optimal solutions exactly parametrize the set. No derivation steps, preservation argument, or verification that the chosen tropical dissimilarity measure yields an exact correspondence are supplied in the abstract; if this duality fails to be bijective on the optima, the polytrope conclusion does not follow.

    Authors: We agree that the abstract, being concise, does not include derivation steps. The full derivation establishing the duality to the min-cost flow problem, including the explicit correspondence of optimal solutions, the preservation of optimality under the tropical dissimilarity, and the bijectivity on the set of optima, appears in Section 3. To address the comment, we will revise the abstract to briefly outline the key steps of the duality argument and expand the relevant section with additional verification that the chosen measure yields an exact parametrization. This will make the polytrope conclusion fully rigorous and self-contained. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper derives the polytrope property of the Fermat-Weber set directly from establishing a duality between the tropical location problem and a minimum-cost flow problem, with the duality serving as the independent mathematical justification rather than a tautology or fitted input. No self-definitional equations, renamed empirical patterns, or load-bearing self-citations appear in the abstract or described chain; the duality is presented as a proven fact internal to the work that parametrizes the set without reducing the claim to its own inputs by construction. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The abstract invokes the existence of a duality between the tropical location problem and min-cost flow without stating additional free parameters or invented entities. Standard tropical semiring axioms are presupposed but not listed as novel.

axioms (1)
  • domain assumption The tropical metric dissimilarity induces a location problem that is dual to a min-cost flow problem on an appropriate graph.
    Invoked in abstract paragraph 3 as the reason the solution set is a polytrope.

pith-pipeline@v0.9.0 · 5633 in / 1311 out tokens · 24061 ms · 2026-05-24T04:07:35.617356+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    Ahuja, Thomas L

    Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network flows: theory, algo- rithms, and applications . Prentice-Hall, Inc., USA, 1993

    work page 1993

  2. [2]

    Aliatimis, R

    G. Aliatimis, R. Yoshida, B. Boyacı, and J. Grants. Tropical logistic regression model on space of phylogenetic trees. Bull Math Biol , 86(99), 2024

    work page 2024

  3. [3]

    Ardila and M

    F. Ardila and M. Develin. Tropical hyperplane arrangements and oriented matroids. Math. Z., 262:795–816, 2009. https://doi.org/10.1007/s00209-008-0400-z

    work page doi:10.1007/s00209-008-0400-z 2009

  4. [4]

    Ardila and C

    F. Ardila and C. J. Klivans. The bergman complex of a matroid and phylogenetic trees. journal of combinatorial theory. Series B, 96(1):38–49, 2006

    work page 2006

  5. [5]

    Brimberg

    J. Brimberg. The Fermat-Weber location problem revisited. Mathematical Programming, 71:71–76, 1995

    work page 1995

  6. [6]

    Tropical convexity in location problems.Math Meth Oper Res, 100:509–534, 2024

    Andrei Comˇ aneci. Tropical convexity in location problems.Math Meth Oper Res, 100:509–534, 2024. 17

    work page 2024

  7. [7]

    Tropical medians by transportation

    Andrei Comˇ aneci and Michael Joswig. Tropical medians by transportation. Mathematical Programming, 205(1–2):813–839, July 2023

    work page 2023

  8. [8]

    The tropical polytope is the set of all weighted tropical fermat- weber points, 2023

    Shelby Cox and Mark Curiel. The tropical polytope is the set of all weighted tropical fermat- weber points, 2023. available at https://arxiv.org/abs/2310.07732

    work page arXiv 2023

  9. [9]

    Criado, M

    F. Criado, M. Joswig, and F. Santos. Tropical bisectors and voronoi diagrams. Found Comput Math, 22:1923–1960, 2022. https://doi.org/10.1007/s10208-021-09538-4

    work page doi:10.1007/s10208-021-09538-4 1923

  10. [10]

    Develin and B

    M. Develin and B. Sturmfels. Tropical convexity. Documenta Math., 9:1–27, 2004

    work page 2004

  11. [11]

    E. A. Dinic. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Mathematics Doklady , 11:1277–1280, 1970

    work page 1970

  12. [12]

    Gavruskin and A

    A. Gavruskin and A. Drummond. The space of ultrametric phylogenetic trees. Journal of Theoretical Biology, 403:197–208, 2016

    work page 2016

  13. [13]

    Gelfand, Mark I

    Israel M. Gelfand, Mark I. Graev, and Alexander Postnikov. Combinatorics of hypergeometric functions associated with positive roots. In V. I. Arnold, I. M. Gelfand, V. S. Retakh, and M. Smirnov, editors, The Arnold-Gelfand Mathematical Seminars , pages 205–221, Boston, MA, 1997. Birkh¨ auser Boston

    work page 1997

  14. [14]

    Goldberg, Sagi Hed, Haim Kaplan, and Robert E

    Andrew V. Goldberg, Sagi Hed, Haim Kaplan, and Robert E. Tarjan. Minimum-cost flows in unit-capacity networks. Theory of Computing Systems , 61(4):987–1010, 11 2017. Copyright - Theory of Computing Systems is a copyright of Springer, 2017; Last updated - 2024-11-23

    work page 2017

  15. [15]

    Goldberg and Robert E

    Andrew V. Goldberg and Robert E. Tarjan. Finding minimum-cost circulations by successive approximation. Mathematics of Operations Research, 15(3):430–466, 1990

    work page 1990

  16. [16]

    P. M. Huggins, W. Li, D. Haws, T. Friedrich, J. Liu, and R. Yoshida. Bayes Estimators for Phylogenetic Reconstruction. Systematic Biology, 60(4):528–540, 04 2011

    work page 2011

  17. [17]

    Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM (JACM), 24(1):1–13, 1977

    work page 1977

  18. [18]

    M. Joswig. Tropical halfspaces. Combinatorial and computational geometry , 52(1):409–431, 2005

    work page 2005

  19. [19]

    Essentials of Tropical Combinatorics

    Michael Joswig. Essentials of Tropical Combinatorics . Springer, New York, NY, 2021

    work page 2021

  20. [20]

    Tropical and ordinary convexity combined

    Michael Joswig and Katja Kulas. Tropical and ordinary convexity combined. Advances in Geometry, 10(2):333–352, 2010

    work page 2010

  21. [21]

    B. Lin, B. Sturmfels, X. Tang, and R. Yoshida. Convexity in tree spaces. SIAM Discrete Math, 3:2015–2038, 2017

    work page 2015

  22. [22]

    Tropical fermat-weber points

    Bo Lin and Ruriko Yoshida. Tropical fermat-weber points. SIAM J. Discret. Math. , 32:1229– 1245, 2018

    work page 2018

  23. [23]

    Maclagan and B

    D. Maclagan and B. Sturmfels. Introduction to Tropical Geometry, volume 161 of Graduate Studies in Mathematics . Graduate Studies in Mathematics, 161, American Mathematical Society, Providence, RI, 2015

    work page 2015

  24. [24]

    A faster strongly polynomial minimum cost flow algorithm

    James Orlin. A faster strongly polynomial minimum cost flow algorithm. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing , STOC ’88, page 377–387, New York, NY, USA, 1988. Association for Computing Machinery

    work page 1988

  25. [25]

    Max-plus definite matrix closures and their eigenspaces

    Sergei ˘ Sergeev. Max-plus definite matrix closures and their eigenspaces. Linear Algebra and its Applications, 421(2):182–201, 2007. Special Issue in honor of Miroslav Fiedler

    work page 2007

  26. [26]

    Speyer and B

    D. Speyer and B. Sturmfels. Tropical mathematics. Mathematics Magazine, 82:163–173, 2009

    work page 2009

  27. [27]

    Tropical gradient descent, 2024

    Roan Talbut and Anthea Monod. Tropical gradient descent, 2024

    work page 2024

  28. [28]

    A strongly polynomial minimum cost circulation algorithm

    Eva Tardos. A strongly polynomial minimum cost circulation algorithm. Combinatorica, 1985. 18

    work page 1985

  29. [29]

    Weiszfeld

    E. Weiszfeld. Sur le point par lequel la somme des distances de n points donnves est minimum. Tohoku Mathematics Journal, 43:355–386, 1937

    work page 1937

  30. [30]

    G¨ unter M. Ziegler. Fans, Arrangements, Zonotopes, and Tilings , pages 191–230. Springer New York, New York, NY, 1995. 19

    work page 1995