pith. sign in

arxiv: 2402.14287 · v6 · pith:F3SH3DIFnew · 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.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Tropical Fermat--Weber Problems over Non-Finite Data and their Inverse Formulations

    math.CO 2026-06 unverdicted novelty 4.0

    Extends tropical Fermat-Weber problems to non-finite data and supplies LP formulations for inverse problems using the one-infinity pseudonorm.