Voronoi polytopes for polyhedral norms on lattices

A polyhedral norm   is a norm NN on RnRn for which the set N(x)≤1N(x)≤1 is a polytope. This covers the case of the L1L1 and L∞L∞ 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 VNVN-spaces. The Voronoi polytopes and other geometrical information are easily obtained from it.