Voronoi Polytopes for Polyhedral Norms on Lattices

2013/12/30 by Deza, Michel, Sikirić, Mathieu Dutour
#Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.1401.0040

Abstract

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

Related

• Voronoi Cells of Lattices with Respect to Arbitrary Norms
• Voronoi diagrams of algebraic varieties under polyhedral norms
• Lifts for Voronoi cells of lattices
• Solving the Closest Vector Problem with respect to l_p Norms
• Voronoi cells of discrete point sets