  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 $VN$-spaces}. The Voronoi polytopes and other
geometrical information are easily obtained from it.
