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=\binom{N}{2}$) 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 with 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.

Publication
SIAM Journal on Discrete Mathematics, 2018, 32(2), 1229–1245
Bo Lin
Bo Lin
Visiting Assistant Professor

My research interests include mathematical biology, tropical geometry and combinatorics.

Ruriko Yoshida
Ruriko Yoshida
Associate Professor

Related