Voronoi Polytopes for Polyhedral Norms on Lattices
arXiv:1401.0040
Abstract
A polyhedral norm is a norm N on R^n for which the set N(x)\leq 1 is a polytope. This covers the case of the L^1 and L^{\infty} norms. We consider here effective algorithms for determining the Voronoi polytope for such norms with a point set being a lattice. The algorithms, that we propose, use the symmetries effectively in order to compute a decomposition of the space into convex polytopes named {\em -spaces}. The Voronoi polytopes and other geometrical information are easily obtained from it.
18 pages, 3 figures