Voronoi polytopes for polyhedral norms on lattices (Q499359)

A polyhedral norm is a norm \(N\) on \(R^n\) for which the set \(N(x)=1\) is a polytope. In particular, the norms \(L^1\) and \(L^\infty\) are polyhedral. In this paper, the authors write explicit effective algorithms for determining the Voronoi polytope for polyhedral norms arising for the sets of lattice nodes. The main idea of the algorithms is to use symmetries that allow to effectively compute a decomposition of the space into nice convex polytopes (\(VN\)-spaces). Knowing such decomposition one can easily obtain the Voronoi polytopes and some other geometrical information.