×

Voronoi polytopes for polyhedral norms on lattices. (English) Zbl 1342.52015

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.

MSC:

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

Software:

4ti2; cdd
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Agarwal, P. K.; Sharir, M., Arrangements and their Applications, (Handbook of Computational Geometry (1998))
[2] Anderson, D. H.; Osborne, M. R., Discrete linear approximation problems in polyhedral norms, Numer. Math., 26, 179-189 (1976) · Zbl 0335.65003
[3] Barvinok, A.; Johnson, D. S.; Woeginger, G, J.; Woodroofe, R., The maximum traveling salesman problem under polyhedral norms, (Integer Programming and Combinatorial Optimization. Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci., vol. 1412 (1998), Springer: Springer Berlin), 195-201 · Zbl 0910.90259
[4] Boissonnat, J. D.; Nielsen, F.; Nock, R., Bregman Voronoi diagrams, Discrete Comput. Geom., 44, 2, 281-307 (2010) · Zbl 1201.52020
[5] Boissonnat, J. D.; Sharir, M.; Tagansky, B.; Yvinec, M., Voronoi diagrams in higher dimensions under certain polyhedral distance functions, Discrete Comput. Geom., 19, 4, 485-519 (1998) · Zbl 0897.68113
[6] Boissonnat, J. D.; Wormser, C.; Yvinec, M., Curved Voronoi diagrams, (Boissonnat, J. D.; Teillaud, M., Effective Computational Geometry for Curves and Surfaces. Effective Computational Geometry for Curves and Surfaces, Mathematics and Visualization (2006), Springer-Verlag), 67-116 · Zbl 1116.65021
[7] Chew, L. P.; Kedem, K.; Sharir, M.; Tagansky, B.; Welzl, E., Voronoi diagrams of lines in three dimensions under polyhedral convex distance functions, J. Algorithms, 29, 238-255 (1998) · Zbl 0916.68180
[8] Deza, M.; Laurent, M., Geometry of Cuts and Metrics (1997), Springer-Verlag · Zbl 0885.52001
[9] Dinur, I.; Kindler, G.; Safra, S., Approximating CVP to within almost-polynomial factors is NP-hard, Combinatorica, 23, 205-243 (2003) · Zbl 1049.68072
[11] Dutour Sikirić, M.; Schürmann, A.; Vallentin, F., Classification of eight dimensional perfect forms, Electron. Res. Announc. Math. Sci., 13, 21-32 (2007) · Zbl 1186.11039
[12] Dutour Sikirić, M.; Schürmann, A.; Vallentin, F., Complexity and algorithms for computing Voronoi cells of lattices, Math. Comp., 78, 1713-1731 (2009) · Zbl 1215.11067
[13] Fincke, U.; Pohst, M., Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comp., 44, 463-471 (1985) · Zbl 0556.10022
[14] Fu, N.; Hashikura, A.; Imai, H., Geometrical treatment of periodic graphs with coordinate system using axis fiber and an application to a motion planning, (ISVD’12 Proceedings of the 2012 Ninth International Symposium on Voronoi Diagrams in Science and Engineering (2012), IEEE Computer Society: IEEE Computer Society Washington, DC, USA), 115-121
[16] Gruber, P. M., Convex and Discrete Geometry (2007), Springer · Zbl 1139.52001
[17] Gruber, P. M.; Lekkerkerker, C. G., Geometry of Numbers (1987), North Holland · Zbl 0611.10017
[18] Jeong, C. S., Parallel Voronoi diagram in \(L_1 (L_\infty )\) metric on a mesh connected computer, Parallel Comput., 17, 2-3, 241-252 (1991) · Zbl 0731.68095
[19] Koltun, V.; Sharir, M., Polyhedral Voronoi diagrams of polyhedra in three dimensions, Discrete Comput. Geom., 31, 83-124 (2004) · Zbl 1060.68130
[20] Lê, N.-M., Abstract Voronoi diagram in 3-space, J. Comput. System Sci., 68, 41-79 (2004) · Zbl 1072.68111
[21] Lee, D. T.; Wong, C. K., Voronoi diagrams in \(L_1 (L_\infty )\) metrics with 2-dimensional storage applications, SIAM J. Comput., 9, 1, 200-211 (1980) · Zbl 0447.68111
[22] Manjunath, M., The Laplacian lattice of a graph under a simplicial distance function, European J. Combin., 34, 1051-1070 (2013) · Zbl 1285.05091
[23] Okabe, A.; Boots, B.; Sugihara, K.; Chiu, S. N., Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (2000), Wiley · Zbl 0946.68144
[26] Schürmann, A., (Computational Geometry of Positive Definite Quadratic Forms. Computational Geometry of Positive Definite Quadratic Forms, University Lecture Series (2009), American Mathematical Society) · Zbl 1185.52016
[28] Voronoi, G. F., Nouvelles applications des paramètres continus à là théorie des formes quadratiques, Deuxième Mémoire, Recherches sur les parallélloedres primitifs, J. Reine Angew. Math., 134, 198-287 (1908), and 136 (1909) 67-181 · JFM 39.0274.01
[29] Zong, C., Minkowski bisectors, Minkowski cells, and lattice coverings · Zbl 1392.52008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.