  We investigate uniqueness issues that arise in $l^\infty$-optimization to
linear spaces and Bergman fans of matroids. For linear spaces, we give a
polyhedral decomposition of $\mathbb{R}^n$ based on the dimension of the set of
$l^\infty$-nearest neighbors. This implies that the $l^\infty$-nearest neighbor
in a linear space is unique if and only if the underlying matroid is uniform.
For Bergman fans of matroids, we show that the set of $l^\infty$-nearest points
is a tropical polytope and give an algorithm to compute its tropical vertices.
A key ingredient here is a notion of topology that generalizes tree topology.
These results have practical implications for distance-based phylogenetic
reconstruction using the $l^\infty$-metric. We analyze the possible dimensions
of the set of $l^\infty$-nearest equidistant tree metrics to an arbitrary
dissimilarity map and the number of tree topologies represented in this set.
For both 3 and 4-leaf trees, we decompose the space of dissimilarity maps
relative to the tree topologies represented.
