Tropical Fermat-Weber Points over Bergman Fans

Shelby Cox, John Sabol, Roan Talbut, Ruriko Yoshida

Published 2025-05-14Version 1

Given a finite set $[p]:= \{1, \ldots , p\}$, it is well known that the space of all ultrametrics on $[p]$ is the Bergman fan associated to the matroid underlying the complete graph of the vertex set $[p]$. Lin et al.~showed that the set of tropical Fermat-Weber points might not be contained in the space of ultrametrics on $[p]$ even if all input data points are in the space. Here we consider a more general set up and we focus on Fermat-Weber points with respect to the tropical metric over the Bergman fan associated with a matroid with the ground set of $q$ elements. We show that there always exists a Fermat-Weber point in the Bergman fan for data in the Bergman fan and we describe explicitly the set of all Fermat-Weber points in the Bergman fan. Then we introduce the natural extension of the safety radius introduced by Atteson to the set of Fermat-Weber points in the Bergman fan of a matroid.