Tropical Bisectors and Voronoi Diagrams

Criado, Francisco; Joswig, Michael; Santos, Francisco

doi:10.1007/s10208-021-09538-4

dc.contributor.author	Criado, Francisco
dc.contributor.author	Joswig, Michael
dc.contributor.author	Santos, Francisco
dc.contributor.other	Universidad de Cantabria	es_ES
dc.date.accessioned	2023-02-17T15:29:48Z
dc.date.available	2023-02-17T15:29:48Z
dc.date.issued	2022
dc.identifier.issn	1615-3375
dc.identifier.issn	1615-3383
dc.identifier.other	PID2019-106188GB-I00	es_ES
dc.identifier.uri	https://hdl.handle.net/10902/27731
dc.description.abstract	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.	es_ES
dc.description.sponsorship	F. Criado has been supported by Berlin Mathematical School and Einstein Foundation Berlin (EVF-2015-230). M. Joswig has been supported by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy - The Berlin Mathematics Research Center MATH+ (EXC-2046/1, Project ID 390685689); “Symbolic Tools in Mathematics and their Application” (TRR 195/2, Project-ID 286237555); “Facets of Complexity” (GRK 2434). F. Santos has been supported by the Einstein Foundation Berlin (EVF-2015-230) and by Grants MTM2017-83750-P/AEI/10.13039/ 501100011033 and PID2019-106188GB-I00/AEI/10.13039/501100011033 of the Spanish State Research Agency.	es_ES
dc.format.extent	38 p.	es_ES
dc.language.iso	eng	es_ES
dc.publisher	Springer New York LLC	es_ES
dc.rights	© The Author(s) 2021	es_ES
dc.rights.uri	http://creativecommons.org/licenses/by/4.0/	*
dc.source	Foundations of Computational Mathematics, 2022, 22, 1923-1960	es_ES
dc.subject.other	Polyhedral norms	es_ES
dc.subject.other	Polytropes	es_ES
dc.subject.other	Randomized algorithms	es_ES
dc.subject.other	Voronoi diagrams	es_ES
dc.title	Tropical Bisectors and Voronoi Diagrams	es_ES
dc.type	info:eu-repo/semantics/article	es_ES
dc.relation.publisherVersion	https://doi.org/10.1007/s10208-021-09538-4	es_ES
dc.rights.accessRights	openAccess	es_ES
dc.identifier.DOI	10.1007/s10208-021-09538-4
dc.type.version	publishedVersion	es_ES