ALGEBRAIC COMBINATORICS

no. 5
Asymmetric tropical distances and power diagrams
Comăneci, Andrei1; Joswig, Michael2
1 Technische Universität Berlin, Chair of Discrete Mathematics/Geometry
2 Technische Universität Berlin, Chair of Discrete Mathematics/Geometry Max-Planck Institute for Mathematics in the Sciences, Leipzig
Algebraic Combinatorics, Volume 6 (2023) no. 5, pp. 1211-1233.

We investigate Voronoi diagrams with respect to an asymmetric tropical distance function, in particular for infinite point sets. These Voronoi diagrams turn out to be much better behaved than those arising from the standard tropical distance, which is symmetric. In particular, we show that the asymmetric tropical Voronoi diagrams may be seen as tropicalizations of power diagrams over fields of real Puiseux series. Our results are then applied to rational lattices and Laurent monomial modules.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.306
Classification: 14T15, 13D02, 46B20, 52B55
Keywords: tropical convexity, polyhedral combinatorics, polyhedral gauge, ordinary and tropical quasi-polyhedron, rational lattice, Delone complex, monomial ideal, Scarf complex
Comăneci, Andrei 1; Joswig, Michael 2

1 Technische Universität Berlin, Chair of Discrete Mathematics/Geometry
2 Technische Universität Berlin, Chair of Discrete Mathematics/Geometry Max-Planck Institute for Mathematics in the Sciences, Leipzig
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2023__6_5_1211_0,
     author = {Com\u{a}neci, Andrei and Joswig, Michael},
     title = {Asymmetric tropical distances and power diagrams},
     journal = {Algebraic Combinatorics},
     pages = {1211--1233},
     publisher = {The Combinatorics Consortium},
     volume = {6},
     number = {5},
     year = {2023},
     doi = {10.5802/alco.306},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.306/}
}
TY  - JOUR
AU  - Comăneci, Andrei
AU  - Joswig, Michael
TI  - Asymmetric tropical distances and power diagrams
JO  - Algebraic Combinatorics
PY  - 2023
SP  - 1211
EP  - 1233
VL  - 6
IS  - 5
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.306/
DO  - 10.5802/alco.306
LA  - en
ID  - ALCO_2023__6_5_1211_0
ER  - 
%0 Journal Article
%A Comăneci, Andrei
%A Joswig, Michael
%T Asymmetric tropical distances and power diagrams
%J Algebraic Combinatorics
%D 2023
%P 1211-1233
%V 6
%N 5
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.306/
%R 10.5802/alco.306
%G en
%F ALCO_2023__6_5_1211_0
Comăneci, Andrei; Joswig, Michael. Asymmetric tropical distances and power diagrams. Algebraic Combinatorics, Volume 6 (2023) no. 5, pp. 1211-1233. doi : 10.5802/alco.306. https://alco.centre-mersenne.org/articles/10.5802/alco.306/

[1] Allamigeon, Xavier; Benchimol, Pascal; Gaubert, Stéphane; Joswig, Michael Log-barrier interior point methods are not strongly polynomial, SIAM J. Appl. Algebra Geom., Volume 2 (2018) no. 1, pp. 140-178 | DOI | MR | Zbl

[2] Allamigeon, Xavier; Benchimol, Pascal; Gaubert, Stéphane; Joswig, Michael What tropical geometry tells us about the complexity of linear programming, SIAM Rev., Volume 63 (2021) no. 1, pp. 123-164 | DOI | MR | Zbl

[3] Amini, Omid; Manjunath, Madhusudan Riemann-Roch for sub-lattices of the root lattice A n , Electron. J. Combin., Volume 17 (2010) no. 1, Paper no. 124, 50 pages | MR | Zbl

[4] Aurenhammer, Franz Power diagrams: properties, algorithms and applications, SIAM J. Comput., Volume 16 (1987) no. 1, pp. 78-96 | DOI | MR

[5] Aurenhammer, Franz Improved algorithms for discs and balls using power diagrams, J. Algorithms, Volume 9 (1988) no. 2, pp. 151-161 | DOI | MR | Zbl

[6] Aurenhammer, Franz; Klein, Rolf; Lee, Der-Tsai Voronoi diagrams and Delaunay triangulations, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2013 | DOI | MR

[7] Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise Algorithms in real algebraic geometry, Algorithms and Computation in Mathematics, 10, Springer-Verlag, Berlin, 2006 | MR

[8] Bayer, Dave; Sturmfels, Bernd Cellular resolutions of monomial modules, J. Reine Angew. Math., Volume 502 (1998), pp. 123-140 | DOI | MR | Zbl

[9] Blömer, Johannes; Kohn, Kathlén Voronoi cells of lattices with respect to arbitrary norms, SIAM J. Appl. Algebra Geom., Volume 2 (2018) no. 2, pp. 314-338 | DOI | MR | Zbl

[10] Boissonnat, Jean-Daniel; Sharir, Micha; Tagansky, Boaz; Yvinec, Mariette Voronoi diagrams in higher dimensions under certain polyhedral distance functions, Discrete Comput. Geom., Volume 19 (1998) no. 4, pp. 485-519 | DOI | MR | Zbl

[11] Boissonnat, Jean-Daniel; Yvinec, Mariette Algorithmic geometry, Cambridge University Press, Cambridge, 1998 (Translated from the 1995 French original by Hervé Brönnimann) | DOI | MR

[12] Cohen, Guy; Gaubert, Stéphane; Quadrat, Jean-Pierre Duality and separation theorems in idempotent semimodules, Linear Algebra Appl., Volume 379 (2004), pp. 395-422 (Tenth Conference of the International Linear Algebra Society) | DOI | MR | Zbl

[13] Comăneci, Andrei; Joswig, Michael Tropical medians by transportation, 2022 (forthcoming, Math. Programming) | arXiv

[14] Conway, John H.; Sloane, Neil J. A. The cell structures of certain lattices, Miscellanea mathematica, Springer, Berlin, 1991, pp. 71-107 | DOI | MR | Zbl

[15] Criado, Francisco; Joswig, Michael; Santos, Francisco Tropical bisectors and Voronoi diagrams, Found. Comput. Math., Volume 22 (2022) no. 6, pp. 1923-1960 | DOI | MR | Zbl

[16] Develin, Mike; Yu, Josephine Tropical polytopes and cellular resolutions, Experiment. Math., Volume 16 (2007) no. 3, pp. 277-291 | DOI | MR | Zbl

[17] Edelsbrunner, Herbert; Seidel, Raimund Voronoĭ diagrams and arrangements, Discrete Comput. Geom., Volume 1 (1986) no. 1, pp. 25-44 | DOI | MR | Zbl

[18] Ehrgott, Matthias Multicriteria optimization, Springer-Verlag, Berlin, 2005 | MR

[19] Fejes Tóth, L. Regular figures, A Pergamon Press Book, The Macmillan Company, New York, 1964 | MR

[20] Gaubert, Stéphane; Katz, Ricardo D. Minimal half-spaces and external representation of tropical polyhedra, J. Algebraic Combin., Volume 33 (2011) no. 3, pp. 325-348 | DOI | MR | Zbl

[21] Gruber, Peter M. Convex and discrete geometry, Grundlehren der mathematischen Wissenschaften, 336, Springer, Berlin, 2007 | MR

[22] Hardy, G. H.; Wright, E. M. An introduction to the theory of numbers, Oxford University Press, Oxford, 2008 | MR

[23] Herzog, Jürgen; Hibi, Takayuki Monomial ideals, Graduate Texts in Mathematics, 260, Springer-Verlag London, Ltd., London, 2011 | DOI | MR

[24] Imai, Hiroshi; Iri, Masao; Murota, Kazuo Voronoĭ diagram in the Laguerre geometry and its applications, SIAM J. Comput., Volume 14 (1985) no. 1, pp. 93-105 | DOI | MR | Zbl

[25] Joswig, Michael Essentials of tropical combinatorics, Graduate Studies in Mathematics, 219, American Mathematical Society, Providence, RI, 2021 | DOI

[26] Joswig, Michael; Loho, Georg Monomial tropical cones for multicriteria optimization, SIAM J. Discrete Math., Volume 34 (2020) no. 2, pp. 1172-1191 | DOI | MR | Zbl

[27] Klee, Victor Some characterizations of convex polyhedra, Acta Math., Volume 102 (1959), pp. 79-107 | DOI | MR | Zbl

[28] Li, An-Min; Simon, Udo; Zhao, Guosong; Hu, Zejun Global affine differential geometry of hypersurfaces, De Gruyter Expositions in Mathematics, 11, De Gruyter, Berlin, 2015 | DOI | MR

[29] Lin, Bo; Yoshida, Ruriko Tropical Fermat-Weber points, SIAM J. Discrete Math., Volume 32 (2018) no. 2, pp. 1229-1245 | DOI | MR | Zbl

[30] Loho, Georg; Smith, Ben Face posets of tropical polyhedra and monomial ideals, 2019 | arXiv

[31] Maclagan, Diane; Sturmfels, Bernd Introduction to tropical geometry, Graduate Studies in Mathematics, 161, American Mathematical Society, Providence, RI, 2015 | DOI | MR

[32] Manjunath, Madhusudan The Laplacian lattice of a graph under a simplicial distance function, European J. Combin., Volume 34 (2013) no. 6, pp. 1051-1070 | DOI | MR | Zbl

[33] Manjunath, Madhusudan; Sturmfels, Bernd Monomials, binomials and Riemann-Roch, J. Algebraic Combin., Volume 37 (2013) no. 4, pp. 737-756 | DOI | MR | Zbl

[34] Markwig, Thomas A field of generalised Puiseux series for tropical geometry, Rend. Semin. Mat. Univ. Politec. Torino, Volume 68 (2010) no. 1, pp. 79-92 | MR | Zbl

[35] Martini, Horst; Swanepoel, Konrad J. The geometry of Minkowski spaces—a survey. II, Expo. Math., Volume 22 (2004) no. 2, pp. 93-144 | DOI | MR

[36] Miller, Ezra; Sturmfels, Bernd Combinatorial commutative algebra, Graduate Texts in Mathematics, 227, Springer-Verlag, New York, 2005 | MR

[37] Voigt, Ina Kirsten Voronoizellen diskreter Punktmengen, Ph. D. Thesis, TU Dortmund (2008) | Zbl

Cited by Sources: