Voronoi polytopes for polyhedral norms on lattices

DOI10.1016/J.DAM.2014.09.007zbMATH Open1342.52015arXiv1401.0040OpenAlexW2963681185MaRDI QIDQ499359FDOQ499359

Authors: Mathieu Dutour Sikirić, Michel Deza 

Publication date: 30 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1401.0040

Recommendations

• Voronoi cells of lattices with respect to arbitrary norms
• Complexity and algorithms for computing Voronoi cells of lattices
• Voronoi diagrams of algebraic varieties under polyhedral norms
• Polyhedral Voronoi cells
• Free and nonfree Voronoi polyhedra

zbMATH Keywords

enumerationVoronoi polytopesaffine hyperplane arrangements

Mathematics Subject Classification ID

Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Cites Work

• Title not available (Why is that?)
• Convex and Discrete Geometry
• Bregman Voronoi diagrams
• Voronoi diagrams in higher dimensions under certain polyhedral distance functions
• Geometry of cuts and metrics
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computational geometry of positive definite quadratic forms. Polyhedral reduction theories, algorithms, and applications
• The Geometric Stability of Voronoi Diagrams with Respect to Small Changes of the Sites
• Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
• Approximating CVP to within almost-polynomial factors is NP-hard
• Complexity and algorithms for computing Voronoi cells of lattices
• Curved Voronoi diagrams
• Discrete, linear approximation problems in polyhedral norms
• Polyhedral Voronoi diagrams of polyhedra in three dimensions
• Abstract Voronoi diagram in 3-space
• The Laplacian lattice of a graph under a simplicial distance function
• Classification of eight-dimensional perfect forms
• Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
• Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions
• Minkowski bisectors, Minkowski cells and lattice coverings
• Parallel Voronoi diagram in \(L_ 1(L_{\infty})\) metric on a mesh- connected computer

Cited In (16)

• On the Voronoi Regions of Certain Lattices
• Low-dimensional lattices. VI. Voronoi reduction of three-dimensional lattices
• Clustering in Hilbert's projective geometry: the case studies of the probability simplex and the elliptope of correlation matrices
• Orthogonality in generalized Minkowski spaces
• Title not available (Why is that?)
• Proximal Voronoï regions, convex polygons, \& leader unform topology
• Preface
• Voronoi diagrams of algebraic varieties under polyhedral norms
• Voronoi cells of lattices with respect to arbitrary norms
• The contact polytope of the Leech lattice
• Théorie de Voronoï géométrique. Propriétés de finitude pour les familles de réseaux et analogues
• Inhomogeneous extreme forms
• On the co-NP-completeness of the zonotope containment problem
• Minkowski bisectors, Minkowski cells and lattice coverings
• Dual Cones and the Voronoi Algorithm
• Comparing perfect and 2nd Voronoi decompositions: the matroidal locus

Uses Software

• cdd
• 4ti2

This page was built for publication: Voronoi polytopes for polyhedral norms on lattices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q499359)