  In this paper we initiate the study of tropical Voronoi diagrams. We start
out with investigating bisectors of finitely many points with respect to
arbitrary polyhedral norms. For this more general scenario we show that
bisectors of three points are homeomorphic to a non-empty open subset of
Euclidean space, provided that certain degenerate cases are excluded.
Specializing our results to tropical bisectors then yields structural results
and algorithms for tropical Voronoi diagrams.
