{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T00:35:34Z","timestamp":1769042134941,"version":"3.49.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,9,7]],"date-time":"2021-09-07T00:00:00Z","timestamp":1630972800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,9,7]],"date-time":"2021-09-07T00:00:00Z","timestamp":1630972800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006764","name":"Technische Universit\u00e4t Berlin","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006764","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we initiate the study of tropical Voronoi diagrams. We start out with investigating bisectors of finitely many points with respect to arbitrary polyhedral norms. For this more general scenario we show that bisectors of three points are homeomorphic to a non-empty open subset of Euclidean space, provided that certain degenerate cases are excluded. Specializing our results to tropical bisectors then yields structural results and algorithms for tropical Voronoi diagrams. \n<\/jats:p>","DOI":"10.1007\/s10208-021-09538-4","type":"journal-article","created":{"date-parts":[[2021,9,7]],"date-time":"2021-09-07T18:09:59Z","timestamp":1631038199000},"page":"1923-1960","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Tropical Bisectors and Voronoi Diagrams"],"prefix":"10.1007","volume":"22","author":[{"given":"Francisco","family":"Criado","sequence":"first","affiliation":[]},{"given":"Michael","family":"Joswig","sequence":"additional","affiliation":[]},{"given":"Francisco","family":"Santos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,7]]},"reference":[{"key":"9538_CR1","doi-asserted-by":"crossref","unstructured":"Daniele Alessandrini, Logarithmic limit sets of real semi-algebraic sets, Adv. Geom. 13 (2013), no.\u00a01, 155\u2013190. MR 3011539.","DOI":"10.1515\/advgeom-2012-0020"},{"issue":"1","key":"9538_CR2","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1137\/17M1142132","volume":"2","author":"Xavier Allamigeon","year":"2018","unstructured":"Xavier Allamigeon, Pascal Benchimol, St\u00e9phane Gaubert, and Michael Joswig, Log-barrier interior point methods are not strongly polynomial, SIAM J. Appl. Algebra Geom. 2 (2018), no.\u00a01, 140\u2013178.","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"9538_CR3","doi-asserted-by":"crossref","unstructured":"Omid Amini and Madhusudan Manjunath, Riemann-Roch for sub-lattices of the root lattice$$A_n$$, Electron. J. Combin. 17 (2010), no.\u00a01, Research Paper 124, 50. MR 2729373.","DOI":"10.37236\/396"},{"key":"9538_CR4","doi-asserted-by":"crossref","unstructured":"Franz Aurenhammer, Rolf Klein, and Der-Tsai Lee, Voronoi diagrams and Delaunay triangulations, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2013. MR 3186045.","DOI":"10.1142\/8685"},{"key":"9538_CR5","doi-asserted-by":"crossref","unstructured":"Matthew Baker and Serguei Norine, Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math. 215 (2007), no.\u00a02, 766\u2013788. MR 2355607.","DOI":"10.1016\/j.aim.2007.04.012"},{"key":"9538_CR6","doi-asserted-by":"crossref","unstructured":"L.\u00a0Paul Chew and Robert L.\u00a0Scot Dyrsdale\u00a0III, Voronoi diagrams based on convex distance functions, Proceedings of the first annual symposium on Computational geometry, ACM, 1985, pp.\u00a0235\u2013244.","DOI":"10.1145\/323233.323264"},{"key":"9538_CR7","doi-asserted-by":"crossref","unstructured":"Mark de\u00a0Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Computational geometry, third ed., Springer-Verlag, Berlin, 2008, Algorithms and applications. MR 2723879.","DOI":"10.1007\/978-3-540-77974-2"},{"key":"9538_CR8","unstructured":"Jules Depersin, St\u00e9phane Gaubert, and Michael Joswig, A tropical isoperimetric inequality, S\u00e9m. Lothar. Combin. \u2013 FPSAC 2017 \u2013 78B (2017), Art. 27, 12. MR 3678609."},{"key":"9538_CR9","unstructured":"Mike Develin, The moduli space of$$n$$tropically collinear points in$$\\mathbb{R}^d$$, Collect. Math. 56 (2005), no.\u00a01, 1\u201319. MR 2131129."},{"key":"9538_CR10","doi-asserted-by":"crossref","unstructured":"Steven Fortune, A sweepline algorithm for Vorono\u012d diagrams, Algorithmica 2 (1987), no.\u00a02, 153\u2013174. MR895442 (88e:68101).","DOI":"10.1007\/BF01840357"},{"key":"9538_CR11","doi-asserted-by":"crossref","unstructured":"Ewgenij Gawrilow and Michael Joswig, polymake: a framework for analyzing convex polytopes, Polytopes\u2014combinatorics and computation (Oberwolfach, 1997), DMV Sem., vol.\u00a029, Birkh\u00e4user, Basel, 2000, pp.\u00a043\u201373. MR1785292 (2001f:52033).","DOI":"10.1007\/978-3-0348-8438-9_2"},{"key":"9538_CR12","unstructured":"Chan He, Horst Martini, and Senlin Wu, On bisectors for convex distance functions, Extracta Math. 28 (2013), no.\u00a01, 57\u201376. MR 3135681."},{"key":"9538_CR13","doi-asserted-by":"crossref","unstructured":"Christian Icking, Rolf Klein, Ng\u1ecdc-Minh L\u00ea, and Lihong Ma, Convex distance functions in$$3$$-space are different, Fund. Inform. 22 (1995), no.\u00a04, 331\u2013352, Computational geometry (San Diego, CA, 1993). MR 1360951.","DOI":"10.3233\/FI-1995-2242"},{"key":"9538_CR14","doi-asserted-by":"crossref","unstructured":"Christian Icking, Rolf Klein, Ngoc-Minh L\u00ea, Lihong Ma, and Francisco Santos, On bisectors for convex distance functions in 3-space, CCCG, (1999).","DOI":"10.1145\/304893.304982"},{"key":"9538_CR15","doi-asserted-by":"crossref","unstructured":"Philipp Jell, Claus Scheiderer, and Josephine Yu, Real tropicalization and analytification of semialgebraic sets, Int. Math. Res. Not. IMRN (2020), Published online: 29 May 2020.","DOI":"10.1093\/imrn\/rnaa112"},{"key":"9538_CR16","unstructured":"Michael Joswig, Tropical halfspaces, Combinatorial and computational geometry, Math. Sci. Res. Inst. Publ., vol.\u00a052, Cambridge Univ. Press, Cambridge, 2005, pp.\u00a0409\u2013431. MR2178330 (2006g:52012)."},{"key":"9538_CR17","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1515\/advgeom.2010.012","volume":"10","author":"Michael Joswig","year":"2010","unstructured":"Michael Joswig and Katja Kulas, Tropical and ordinary convexity combined, Adv. Geometry 10 (2010), 333\u2013352.","journal-title":"Adv. Geometry"},{"key":"9538_CR18","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1016\/j.laa.2016.02.027","volume":"501","author":"Michael Joswig","year":"2016","unstructured":"Michael Joswig and Georg Loho, Weighted digraphs and tropical cones, Linear Algebra Appl. 501 (2016), 304\u2013343.","journal-title":"Linear Algebra Appl."},{"key":"9538_CR19","doi-asserted-by":"crossref","unstructured":"J.\u00a0J. Kosowsky and Alan\u00a0L. Yuille, The invisible hand algorithm: Solving the assignment problem with statistical physics, Neural Networks 7 (1994), no.\u00a03, 477\u2013490.","DOI":"10.1016\/0893-6080(94)90081-7"},{"key":"9538_CR20","doi-asserted-by":"crossref","unstructured":"Thomas Lam and Alexander Postnikov, Alcoved polytopes. I, Discrete Comput. Geom. 38 (2007), no.\u00a03, 453\u2013478. MR2352704.","DOI":"10.1007\/s00454-006-1294-3"},{"key":"9538_CR21","unstructured":"Anthea Monod, Bo Lin, Ruriko Yoshida, Qiwen Kang, Tropical geometry of phylogenetic tree space: a statistical perspective, (2020), Preprint arXiv:1805.12400v6"},{"key":"9538_CR22","doi-asserted-by":"publisher","first-page":"3287221","DOI":"10.1090\/gsm\/161","volume-title":"Introduction to tropical geometry, Graduate Studies in Mathematics","author":"Diane Maclagan","year":"2015","unstructured":"Diane Maclagan and Bernd Sturmfels, Introduction to tropical geometry, Graduate Studies in Mathematics, vol. 161, American Mathematical Society, Providence, RI, 2015. 3287221"},{"key":"9538_CR23","doi-asserted-by":"crossref","unstructured":"Horst Martini and Konrad\u00a0J Swanepoel, The geometry of Minkowski spaces\u2013a survey. part ii, Expositiones mathematicae 22 (2004), no.\u00a02, 93\u2013144.","DOI":"10.1016\/S0723-0869(04)80009-4"},{"key":"9538_CR24","doi-asserted-by":"crossref","unstructured":"Grigory Mikhalkin, Enumerative tropical algebraic geometry in$$\\mathbb{R}^2$$, J. Amer. Math. Soc. 18 (2005), no.\u00a02, 313\u2013377. 2137980 (2006b:14097).","DOI":"10.1090\/S0894-0347-05-00477-7"},{"key":"9538_CR25","doi-asserted-by":"crossref","unstructured":"David Speyer and Bernd Sturmfels, The tropical Grassmannian, Adv. Geom. 4 (2004), no.\u00a03, 389\u2013411. MR2071813 (2005d:14089)","DOI":"10.1515\/advg.2004.023"},{"key":"9538_CR26","unstructured":"Rade\u00a0T. \u017divaljevi\u0107, Topological methods in discrete geometry, Handbook of Discrete and Computational Geometry (Csaba\u00a0D. T\u00f3th, Jacob\u00a0E. Goodmann, and Joseph O\u2019Rourke, eds.), CRC Press, 2018, 3rd edition."},{"issue":"4","key":"9538_CR27","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1137\/0216049","volume":"16","author":"Peter Widmayer","year":"1987","unstructured":"Peter Widmayer, Ying-Fung Wu, and Chak-Kuen Wong, On some distance problems in fixed orientations, SIAM Journal on Computing 16 (1987), no.\u00a04, 728\u2013746.","journal-title":"SIAM Journal on Computing"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09538-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-021-09538-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09538-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,14]],"date-time":"2022-11-14T23:59:36Z","timestamp":1668470376000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-021-09538-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,7]]},"references-count":27,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["9538"],"URL":"https:\/\/doi.org\/10.1007\/s10208-021-09538-4","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,7]]},"assertion":[{"value":"3 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 May 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 September 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}