Tropical Fermat-Weber points

Abstract

In a metric space, the Fermat-Weber points of a sample are statistics to measure the central tendency of the sample and it is well-known that the Fermat-Weber point of a sample is not necessarily unique in the metric space. We investigate the computation of Fermat-Weber points under the tropical metric on the quotient space ${\mathbb{R}}^n/\mathbb{R}1$ with a fixed $n\in \mathbb{N}$, motivated by its application to the space of equidistant phylogenetic trees with $N$ leaves (in this case $n=\left(\genfrac{}{}{0ex}{}{N}{2}\right)$) realized as the tropical linear space of all ultrametrics. We show that the set of all tropical Fermat-Weber points of a finite sample is always a classical convex polytope, and we present a combinatorial formula for a key value associated to this set. We identify conditions under which this set is a singleton. We apply numerical experiments to analyze the set of the tropical Fermat-Weber points within a space of phylogenetic trees. We discuss the issues in the computation of the tropical Fermat-Weber points.

20 Pages, 2 figures. To appear in SIAM Journal on Discrete Mathematics

References in corpus (4)

• Duality and separation theorems in idempotent semimodules
• The Fermat-Torricelli problem in normed planes and spaces
• Convexity in Tree Spaces
• L-infinity optimization to linear spaces and phylogenetic trees

Cited by in corpus (11)

• Tropical medians by transportation
• Tropical Geometric Variation of Phylogenetic Tree Shapes
• Tropical convexity in location problems
• Fréchet Mean Set Estimation in the Hausdorff Metric, via Relaxation
• Tropical Principal Component Analysis and its Application to Phylogenetics
• Asymmetric tropical distances and power diagrams
• Tropical Data Science
• Breakdown points of Fermat-Weber problems under gauge distances
• Classifying Tree Topologies along Tropical Line Segments
• Tropical Fréchet Means: a polyhedral approach to exact optimization
• Projections of Tropical Fermat-Weber Points