We consider norms in real vector spaces where the unit ball is an arbitrary convex polytope, possibly centrally symmetric.  In contrast with the Euclidean norm, the topological shape of bisectors may be complicated.  Our first main result is a formula for the Betti numbers of bisectors of three points in sufficiently general position.

Specializing our results to the tropical polyhedral norm then yields structural results and algorithms for tropical Voronoi diagrams.  The tropical distance function plays a key role in current applications of tropical geometry.

Joint work with Francisco Criado and Francisco Santos.