  We study Voronoi diagrams of manifolds and varieties with respect to
polyhedral norms. We provide upper and lower bounds on the dimensions of
Voronoi cells. For algebraic varieties, we count their full-dimensional Voronoi
cells. As an application, we consider the polyhedral Wasserstein distance
between discrete probability distributions.
