\documentclass[ALCO,Unicode]{cedram}

\usepackage{bbm}
\usepackage{bm}
\usepackage{xspace}
\usepackage{csquotes}
\usepackage{standalone}

\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{calc}
\usetikzlibrary{cd}
\usetikzlibrary{patterns}

\usepackage{mathbbol}

\newcommand\CC{{\mathbb C}}
\newcommand\EE{{\mathbb E}}
\newcommand\FF{{\mathbb F}}
\newcommand\NN{{\mathbb N}}
\newcommand\KK{{\mathbb K}}
\newcommand\PP{{\mathbb P}}
\newcommand\QQ{{\mathbb Q}}
\newcommand\RR{{\mathbb R}}
\newcommand\Sph{{\mathbb S}}
\newcommand\TT{{\mathbb T}}
\newcommand\ZZ{{\mathbb Z}}

\newcommand\cI{{\mathcal I}}
\newcommand\cP{{\mathcal P}}
\newcommand\cC{{\mathcal C}}
\newcommand\cE{{\mathcal E}}
\newcommand\cS{{\mathcal S}}
\newcommand\cF{{\mathcal F}}
\newcommand\cG{{\mathcal G}}
\newcommand\cH{{\mathcal H}}
\newcommand\cL{{\mathcal L}}
\newcommand\cM{{\mathcal M}}
\newcommand\cT{{\mathcal T}}
\newcommand\cQ{{\mathcal Q}}
\newcommand\cB{{\mathcal B}}

\newcommand\frT{{\mathfrak T}}

\DeclareMathSymbol{\0}{\mathord}{bbold}{`0}
\DeclareMathSymbol{\1}{\mathord}{bbold}{`1}

\newcommand\SetOf[2]{\left\{#1 \mid #2\right\}}
\newcommand\smallSetOf[2]{\{#1 \mid #2\}}
\newcommand\bigSetOf[2]{\bigl\{#1 \bigm| #2\bigr\}}
\newcommand\biggSetOf[2]{\biggl\{#1 \biggm| #2\biggr\}}
\newcommand\BiggSetOf[2]{\Biggl\{#1 \Biggm| #2\Biggr\}}
\newcommand\card[1]{\# #1}
\newcommand\torus[1]{\RR^{#1}/\RR\1}

\newcommand\laurentseries[2]{{#1}(\hskip-.175em({#2})\hskip-.175em)}
\newcommand\puiseuxseries[2]{{#1}\{\hskip-.25em\{#2\}\hskip-.25em\}}
\newcommand\puiseuxseriesCVG[2]{{#1}\{\hskip-.25em\{#2\}\hskip-.25em\}_{\operatorname{cvg}}}
\newcommand\puiseuxfractions[2]{{#1}\{#2\}}
\newcommand\hahnseries[2]{{#1}\{\hskip-.25em\{{#2}^\RR\}\hskip-.25em\}}
\newcommand\hahnfractions[2]{{#1}\{{#2}^\RR\}}

\newcommand\TTmax{\TT^{\max}}
\newcommand\TTmin{\TT^{\min}}
\newcommand\TP{{\TT\PP}}
\newcommand\BergmanFan{{\widetilde B}}

\DeclareMathOperator\dist{dist}
\DeclareMathOperator\conv{conv}
\DeclareMathOperator\tconv{tconv}
\DeclareMathOperator\vol{vol}
\DeclareMathOperator\nvol{nvol}
\DeclareMathOperator\Sym{Sym}
\DeclareMathOperator\Aut{Aut}
\DeclareMathOperator\argmin{arg\,min}
\DeclareMathOperator\argmax{arg\,max}
\DeclareMathOperator\Rev{Rev}
\DeclareMathOperator\id{id}
\DeclareMathOperator\SubDiv{\cS}
\DeclareMathOperator\GF{GF}
\DeclareMathOperator\rk{rk}
\DeclareMathOperator\val{val}
\DeclareMathOperator\tdet{tdet}
\DeclareMathOperator\codim{codim}
\DeclareMathOperator\lcm{lcm}
\DeclareMathOperator\relint{relint}
\DeclareMathOperator\lca{lca}
\DeclareMathOperator\Tr{Tr}
\DeclareMathOperator\SL{SL}

\DeclareMathOperator{\VR}{VR}
\DeclareMathOperator{\VD}{VD}
\DeclareMathOperator{\PR}{PR}
\DeclareMathOperator{\PD}{PD}
\DeclareMathOperator{\bisector}{bis}
\DeclareMathOperator{\FW}{FW}
\DeclareMathOperator\CovDec{CovDec}
\DeclareMathOperator\TGr{TGr}
\DeclareMathOperator{\Del}{Del}
\DeclareMathOperator{\Tan}{Tan}
\DeclareMathOperator{\SecPoly}{\Sigma-poly}

\newcommand\dd[1]{\operatorname{d}_{#1}}

\newcommand\SecFan{{\mathfrak S}}
\newcommand\PSubFan{{\mathfrak P}}

\newcommand\dom{\text{dom}}
\newcommand\supp{\text{supp}}
\newcommand\Trop{\RR \cup \{\infty\}}

\newcommand\transpose[1]{#1^\top}

\newcommand\polymake{\texttt{polymake}\xspace}
\newcommand\TOPCOM{\texttt{TOPCOM}\xspace}
\newcommand\mptopcom{\texttt{mptopcom}\xspace}
\newcommand\Gfan{\texttt{Gfan}\xspace}


\definecolor{tolorange}{RGB}{238,119,51} 
\definecolor{tolblue}{RGB}{0,119,187} 
\definecolor{tolgreen}{RGB}{0,153,136} 
\definecolor{tolpurple}{RGB}{136,34,85} 
\definecolor{ibmyellow}{RGB}{255, 176, 0}
\definecolor{darkgray}{RGB}{64,64,64}

\tikzstyle{blackdot} = [circle,draw=black,fill=black,scale=0.5]




\DeclarePairedDelimiter\abs{\lvert}{\rvert}
\title[Asymmetric tropical distances and power diagrams]{Asymmetric tropical distances and power diagrams}

\author[\initial{A.} Com\u{a}neci]{\firstname{Andrei} \lastname{Com\u{a}neci}}


\address{
	Technische Universit\"{a}t Berlin,
	Chair of Discrete Mathematics/Geometry
}

\email{comaneci@math.tu-berlin.de}

\author[\initial{M.} Joswig]{\firstname{Michael} \lastname{Joswig}}

\address{
	Technische Universit\"{a}t Berlin,
	Chair of Discrete Mathematics/Geometry \\
	Max-Planck Institute for Mathematics in the Sciences, Leipzig
}

\email{joswig@math.tu-berlin.de}

\thanks{Support by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's Excellence Strategy -- The Berlin Mathematics Research Center MATH$^+$ (EXC-2046/1, project ID 390685689) gratefully acknowledged.
	M.~Joswig has further been supported by \enquote{Symbolic Tools in Mathematics and their Application} (TRR 195, project-ID 286237555).
	A.~Com\u{a}neci was supported by \enquote{Facets of Complexity} (GRK 2434, project-ID~385256563).}


\keywords{tropical convexity; polyhedral combinatorics; polyhedral gauge; ordinary and tropical quasi-polyhedron; rational lattice; Delone complex; monomial ideal; Scarf complex}


\subjclass{14T15, 13D02, 46B20, 52B55}


\begin{document}
	
	\begin{abstract}
		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.
	\end{abstract}
	
	\maketitle
	
	\section{Introduction}
	
	The asymmetric tropical distance function is the polyhedral norm on the quotient vector space $\torus{n}$ induced by the regular simplex $\conv\{e_1,e_2,\dots,e_n\}$.
	In this way, this is a special case of a polyhedral norm with respect to a polytope which is not centrally symmetric; \cf \cite[Sect.~7.2]{AurenhammerKleinLee:2013} and \cite[Sect.~4]{MartiniSwanepoel:2004}.
	Such a not necessarily symmetric norm is also called a \enquote{polyhedral gauge.}
	The asymmetric tropical distance function and the resulting Voronoi diagrams were studied by Amini and Manjunath~\cite{RRlattice} and Manjunath~\cite{LapLatticeGraph} in the context of tropical versions of the Riemann--Roch theorem for algebraic curves.
	Recently, we analyzed the Fermat--Weber problem for the same distance function \cite{ComaneciJoswig:2205.00036}.
	For general introductions to tropical geometry see \cite{Tropical+Book} and \cite{ETC}.
	
	One motivation for this work is a recent trend to exploit metric properties of tropical linear spaces and more general tropical varieties for applications in optimization and data science.
	Usually, these results employ the tropical distance function $\dist(a,b) = \max (a_i-b_i) - \min (a_j-b_j)$, which is symmetric.
	That symmetry seems to suggest that this is the natural distance function to work with.
	Moreover, the tropical distance function has a history as \enquote{Hilbert's projective metric}, which was investigated, \eg by Cohen, Gaubert and Quadrat \cite{CohenGaubertQuadrat04}.
	Yet here we gather further evidence that its asymmetric sibling is actually better behaved, geometrically and algorithmically.
	This is in line with the observation that the asymmetric tropical Fermat--Weber problem \cite{ComaneciJoswig:2205.00036} is more benign than its symmetric counterpart, which was considered by Lin and Yoshida~\cite{Lin-Yoshida:2018}.
	
	Our contributions include the following.
	First, we extend the study of the polyhedral geometry of the Voronoi diagrams with respect to the asymmetric tropical distance, a topic which arose in \cite{RRlattice}.
	We explicitly admit point sets which are infinite.
	For instance, the bisectors turn out to be tropically convex and thus contractible.
	This is very different from the symmetric case, where topologically nontrivial bisectors do occur \cite[Example~3]{TropBis}.
	We prove that, locally, the asymmetric tropical Voronoi regions of a discrete set of sites behave like (possibly unbounded) tropical polyhedra (Proposition~\ref{prop:trop-quasi}); yet globally this is not true in general.
	This leads us to defining a new notion of \emph{super-discreteness}, for which we can show that the asymmetric tropical Voronoi regions do form tropical polyhedra (Theorem~\ref{th:polySuperDisc}).
	This includes finite sets and rational lattices as special cases.
	
	As a second main result, we prove that the asymmetric tropical Voronoi diagrams arise as tropicalizations of power diagrams over fields of real Puiseux series (Theorem~\ref{th:PuiseuxLift}).
	In this way we further explore the connection between tropical convexity and ordinary polyhedral geometry over ordered fields; see \cite[\textsection 2]{DevelinYu07}, \cite[\S2]{ABGJ:SIREV} and \cite[\textsection 5.2]{ETC}.
	The relationship between tropical Voronoi diagrams and ordinary power diagrams is also reminiscent of the classical construction of Euclidean Voronoi diagrams through projecting a convex polyhedron whose facets are tangent to the standard paraboloid.
	Power diagrams generalize Voronoi diagrams much like regular subdivisions generalize Delone subdivisions of point sets in Euclidean space \cite[\textsection 4]{PowDiag}.
	A similar construction for Voronoi diagrams with respect to the symmetric tropical distance is unknown and seems unlikely to exist.
	Edelsbrunner and Seidel investigated Voronoi diagrams for very general distance functions \cite{Edelsbrunner+Seidel:1986}.
	Their construction differs from the one developed by Amini and Manjunath \cite{RRlattice}, which we adopt here.
	Yet, it turns out that for discrete sets in general position both notions agree (Theorem~\ref{thm:V-cells}).
	
	Finally, we define \emph{asymmetric tropical Delone complexes}.
	These are abstract simplicial complexes, which may be somewhat unwieldy in general.
	For sites in general position, however, this corresponds to an ordinary Delone triangulation over Puiseux series.
	This is interesting because Scarf complexes of Laurent monomial modules arise as special cases (Corollary~\ref{cor:scarf}).
	These occur as supports of resolutions in commutative algebra \cite{BayerSturmfels:1998,CombCommAlg}.
	
	Delone complexes are named after the Russian mathematician Boris Nikolayevich Delone (1880--1980), whose name is sometimes written \enquote{Delaunay.}
	Delone himself used both spellings in his articles.
	
	\longthanks{We thank Omid Amini, Dan Corey, Georg Loho and two anonymous reviewers for their comments.}

	
	\section{Directed distances and polyhedral norms}
	
	We start out by fixing our notation.
	Consider a polytope $K \subset \RR^n$ with the origin in its interior; the existence of an interior point entails that $\dim K=n$.
	For $a,b\in\RR^n$ let $d_K(a,b)$ be the unique real number $\alpha>0$ such that $b-a \in \partial (\alpha K)$, where $\alpha K$ is $K$ scaled by $\alpha$.
	We call this the \emph{(polyhedral) directed distance} from $a$ to $b$ with respect to $K$.
	The function $d_K$ satisfies the triangle inequality, and it is translation invariant and homogeneous with respect to scaling by positive reals.
	If additionally $K$ is centrally symmetric, \ie $K=-K$, then $d_K(a,b)=d_K(b,a)$.
	Consequently, in this case $d_K$ is a metric, and $d_K(\cdot,\0)$ is a norm on $\RR^n$.
	Norms which arise in this way are called \emph{polyhedral}; see \cite[Sect.~7.2]{AurenhammerKleinLee:2013} and \cite[Sect.~4]{MartiniSwanepoel:2004}.
	We write $\0$ for the all zeros and~$\1$ for the all ones vectors (of length $n$), respectively.
	The \emph{asymmetric tropical distance} in $\RR^n$ is given by
	\begin{equation}\label{eq:dtriangle}
		d_\triangle(a,b) \ = \ \sum_{i\in[n]} (b_i - a_i) - n \min_{i\in[n]}(b_i-a_i) \ = \ \sum_{i\in[n]} (b_i -a_i) + n \max_{i\in[n]}(a_i-b_i) \enspace ,
	\end{equation}
	where $a, b\in\RR^n$.
	Since $d_\triangle(a',b')=d_\triangle(a,b)$ for $a-a'\in\RR\1$ and $b-b'\in\RR\1$, this induces the directed distance with respect to the standard simplex $\triangle=\conv\{e_1,\dots,e_n\}+\RR\1$ in the $(n{-}1)$-dimensional quotient vector space $\torus{n}$, which is the \emph{tropical projective torus}.
	We do not distinguish between these two functions and call the latter directed distance function also the \emph{asymmetric tropical distance} in $\torus{n}$.
	
	The \emph{(symmetric) tropical distance} between $a,b\in\RR^n$ (or $\torus{n}$) is more common.
	It is defined as
	\[
	\dist(a,b) \ = \ \max_{i\in[n]} \left(a_i-b_i\right) - \min_{j\in[n]} \left(a_j-b_j\right) \ = \ \max_{i,j\in[n]}(a_i-b_i-a_j+b_j) \enspace ;
	\]
	\cf \cite[\textsection 5.3]{ETC}.
	The symmetric and asymmetric tropical distances are related by
	\[
	\begin{aligned}
		\dist(a,b) \ &= \ \tfrac{1}{n}\left(d_{\triangle}(a,b) + d_\triangle(b,a)\right) \quad \text{and}\\
		\dist(a,b) \ &\leq \ d_\triangle(a, b) \ \leq \ (n-1)\dist(a,b) \enspace ,
	\end{aligned}
	\]
	where the two inequalities are both tight.
	
	\section{Asymmetric tropical Voronoi regions}
	\label{sec:regions}

	In this section we will investigate Voronoi diagrams with respect to the asymmetric tropical distance function.
	Our results extend the work of Amini and Manjunath \cite[\textsection 4.2]{RRlattice}, who study these Voronoi diagrams for points located in a sub-lattice of a root lattice of type $A$.
	In a way, here we pick up the suggestion in \cite[Remark 4.9]{RRlattice}, which asked to make the connection to tropical convexity.
	
	It will be convenient to work with special coordinates in $\torus{n}$.
	For this, we consider the tropical hypersurface
	\[
	\cH \ := \SetOf{x\in\RR^n}{ x_1+x_2+\cdots+x_n=0 } \enspace ,
	\]
	which is an ordinary linear hyperplane in $\RR^n$.
	The hyperplane $\cH$ occurs as \enquote{$H_0$} in \cite{RRlattice}.
	Observe that $-\cH=\cH$ is centrally symmetric.
	This makes $\cH$ a tropical hyperplane with respect to both choices of the tropical addition, $\max$ and $\min$; \cf \cite[\textsection 1.3]{ETC}.
	Moreover, each point $x+\RR\1\in\torus{n}$ has a unique representative with $\sum x_i=0$.
	This gives a linear isomorphism $\torus{n}\cong\cH$ that will be used throughout the paper.
	In fact, we will state most of our results using $\cH$ instead of $\torus{n}$ to emphasize this identification.
	
	For our arithmetic we consider the \emph{$\max$-tropical semiring} $\TT=(\RR\cup\{-\infty\},\oplus,\odot)$, where $\oplus=\max$ is the tropical addition, and $\odot=+$ is the tropical multiplication.
	The additive neutral element is $-\infty$, and $0$ is neutral with respect to the tropical multiplication.
	A (homogeneous) \emph{tropical linear inequality} is
	\[
	\bigoplus_{i\in I} a_i\odot x_i \ \leq \ \bigoplus_{j\in J} b_j\odot x_j \enspace ,
	\]
	where $a_i,b_j\in\RR$, and $I,J$ are disjoint nonempty subsets of $[n]$.
	The set of solutions is a \emph{$\max$-tropical halfspace} in $\torus{n}$ (or $\cH$).
	A \emph{tropical polyhedron} is the intersection of finitely many tropical halfspaces; see\ \cite[\textsection 7.2]{ETC}.
	A nonempty set $C\subset\RR^n$ is a \emph{tropical cone} if for all $x,y\in C$ and $\lambda,\mu\in\RR$ we have $\lambda{\odot}x \oplus \mu{\odot}y\in C$.
	Each tropical cone contains $\RR\1$, whence we may equivalently study its canonical projection to $\torus{n}$, which is a \emph{tropically convex} set; \cf \cite[\textsection 5.2]{ETC}.
	
	Let $S\subset\torus{n}$ be a nonempty discrete set of points, which is possibly infinite.
	Following common practice in computational geometry, the points in $S$ will be called the \emph{sites}.
	Throughout, we will measure distances via the asymmetric tropical distance function $d_\triangle$.
	The \emph{(asymmetric tropical) Voronoi region} of a site $a\in S$ is the set
	\begin{equation} \label{eq:defVR}
		\VR_S(a) \ := \ \bigSetOf{x\in\cH}{d_\triangle(x,a) \leq d_\triangle(x,b) \text{ for all } b\in S} \enspace .
	\end{equation}
	For two distinct sites $a,b\in\cH$ we abbreviate $h(a,b)=\VR_{\{a,b\}}(a)$.
	This notation yields $\VR_S(a)=\bigcap_{b\in S\setminus\{a\}} h(a,b)$.
	The analysis of asymmetric tropical Voronoi regions starts with the following basic observation, which is similar to \cite[Lemma~1]{Gaubert+Katz:2011}.
	\begin{proposition}\label{prop:VR-pair}
		For two distinct points $a,b\in\cH$ the Voronoi region $h(a,b)$ is a $\max$-tropical halfspace.
	\end{proposition}
	\begin{proof}
		The inequality $d_\triangle(x,a) \leq d_\triangle(x,b)$ translates into
		\[
		n \max_{i\in[n]}(x_i-a_i) \ \leq \  n \max_{i\in[n]}(x_i-b_i) \enspace.
		\]
		Then the above inequality is equivalent to
		\begin{equation}\label{eq:VR-pair:ineq}
			\bigoplus_{i\in[n]} (-a_i) \odot x_i \ \leq \ \bigoplus_{i\in[n]} (-b_i) \odot x_i \enspace .
		\end{equation}
		Since further $a\neq b$, the difference $a-b$ must have positive as well as negative coordinates.
		Consequently, the set $I:=\smallSetOf{i\in[n]}{a_i<b_i}$ is a nonempty and proper subset of $[n]$.
		We will show that \eqref{eq:VR-pair:ineq} is equivalent to
		\begin{equation}\label{eq:VR-pair:halfspace}
			\bigoplus_{i\in I} (-a_i) \odot x_i \ \leq \ \bigoplus_{i\not\in I} (-b_i) \odot x_i \enspace .
		\end{equation}
		Suppose that $x\in\cH$ satisfies \eqref{eq:VR-pair:ineq}.
		Let $k,\ell\in[n]$ be indices with $\max (-a_i + x_i)=-a_k + x_k \leq -b_\ell + x_\ell = \max (-b_i + x_i)$.
		We distinguish two cases.
		Either $k\in I$, whence $-a_k>-b_k$ and thus $\ell\not\in I$; so $x$ satisfies \eqref{eq:VR-pair:halfspace}.
		Or $k\not\in I$, whence $-a_k\leq -b_k$; in this case $x$ trivially satisfies \eqref{eq:VR-pair:halfspace}.
		This argument can be reverted, which proves the reverse implication.
		The homogeneous max-tropical linear inequality \eqref{eq:VR-pair:halfspace} describes a max-tropical linear halfspace.
	\end{proof}
	The above result has a direct consequence, which sharpens \cite[Lemma~4.4]{RRlattice}.
	
	\begin{corollary}
		For an arbitrary finite set of sites $S\subset\cH$ and $a\in S$ the Voronoi region $\VR_S(a)$ is a $\max$-tropical tropical polyhedron.
	\end{corollary}
	\begin{proof}
		We have $\VR_S(a) = \bigcap_{b\in S\setminus\{a\}} h(a,b)$, and thus the claim follows from the previous result.
	\end{proof}
	
	We define the \emph{(asymmetric tropical) Voronoi diagram} of $S$, denoted $\VD(S)$, as the intersection poset generated by the Voronoi regions.
	The intersections of nonempty families of Voronoi regions are the \emph{(asymmetric tropical) Voronoi cells}.
	These form the elements of $\VD(S)$, and they are partially ordered by inclusion.
	The \emph{(asymmetric tropical) bisector} of $S$ is the set
	\[
	\bisector(S) \ = \ \bigSetOf{x\in\cH}{d_\triangle(x,a) = d_\triangle(x,b) \text{ for all } a,b\in S} \ = \ \bigcap_{a\in S} \VR_S(a) \enspace .
	\]
	We have the following basic topological information about bisectors and Voronoi cells.
	\begin{corollary}
		Any bisector $\bisector(S)$ and any cell of $\VD(S)$ is $\max$-tropically convex and hence contractible or empty.
	\end{corollary}
	\begin{proof}
		The boundary plane of a tropical halfspace is tropically convex \cite[Observation~7.5]{ETC}.
		The intersection of tropically convex sets is tropically convex.
		Nonempty tropically convex sets are contractible \cite[Proposition~5.22]{ETC}.
	\end{proof}
	
	\begin{remark}
		By \cite[Theorem~7.11]{ETC} the closure of any bisector or Voronoi cell in the tropical projective space is a tropical polytope.
		This is in stark contrast with the situation in symmetric tropical Voronoi diagrams, which allow for topologically nontrivial bisectors; \cf \cite[Example~3]{TropBis}.
	\end{remark}
	
	Euclidean Voronoi regions for a general discrete set need not be polyhedral, but they are always \emph{quasi-polyhedra}, \ie their intersections with polytopes yield polytopes~\cite[Proposition~32.1]{Gruber:2007}.
	The next example shows that the situation is similar in the tropics.
	Comprehensive discussions on Euclidean Voronoi diagrams can be found in~\cite{Voigt:2008} and~\cite{AurenhammerKleinLee:2013}.
	
	\begin{figure}[t]
		\centering
		\includestandalone[width=0.35\linewidth]{figures/discreteNonPolyhedral}
		\caption{The non-polyhedral Voronoi region $\VR_S(\0)$ from Example~\ref{ex:nonpolyh}, for $a=5$.}
		\label{fig:discrete-nonpolyhedral}
	\end{figure}
	
	\begin{example} \label{ex:nonpolyh}
		For a fixed positive real number $a$, consider the infinite set
		\[ S \ = \ \{\0\}\cup\SetOf{\left(n+\tfrac{a}{n},-\tfrac{a}{n},-n\right)}{n\in\ZZ_{>0}} \enspace, \]
		which is discrete.
		Then the Voronoi cell $\VR_S(\0)$ is defined by the inequalities $x_1\leq\max(x_2+\tfrac{a}{n},x_3+n)$ for all positive integers $n$.
		None of these are redundant.
		Therefore, $\VR_S(\0)$ is not a tropical polyhedron; see Figure~\ref{fig:discrete-nonpolyhedral}.
		The boundary of this Voronoi region is piecewise linear, with infinitely many straight pieces.
		The boundary for the symmetric tropical Voronoi region about $\0$ has a similar shape, but its pieces come from boundaries of semi-polytropes; \cf \cite[\textsection 4.4]{Tropical+Book}.
	\end{example}
	
	A point set $S\subset\cH$ is in \emph{general position} if for any pair of distinct sites $a,b\in S$ we have $a_i\neq b_i$ for all $i\in[n]$.
	The following observation is similar to \cite[Proposition~2]{TropBis}, which is about the symmetric tropical distance function.
	\begin{lemma}\label{lem:bisector-generic}
		For two distinct points $a,b\in\cH$ in general position, the two point bisector $\bisector(a,b)$ is the boundary plane of a $\max$-tropical halfspace.
		In particular, it is an ordinary polyhedral complex of codimension one.
	\end{lemma}
	\begin{proof}
		If $a$ and $b$ are in general position, then the proof of Proposition~\ref{prop:VR-pair} shows that the bisector $\bisector(a,b)$ is the intersection of two opposite tropical halfspaces.
		In particular, $\bisector(a,b)$ is the boundary of a tropical halfspace; \cf \cite[p.~193]{ETC}.
	\end{proof}
	
	The assumption of general position is needed in Lemma~\ref{lem:bisector-generic}, as the next example shows.
	\begin{example} \label{exmp:non-generic}
		Consider $a=(-6,-5,11)$ and $b=(-5,12,-7)$, which are in general position.
		The bisector $\bisector(a,b)$ is the boundary of a $\max$-tropical halfspace with apex $\min(a,b)=(-6,-5,-7)\in\torus{3}$, whose representative in $\cH$ is $(0,1,-1)$.
		However, the points $c=(-5,-5,10)$ and $d=(-5,10,-5)$ are not in general position.
		The bisector $\bisector(c,d)$ contains the entire $\max$-tropical hyperplane with apex $\min(c,d)=(-5,-5,-5)=(0,0,0)$ and the sector $\smallSetOf{x}{x_1\geq\max(x_2,x_3)}$.
		Both cases are illustrated in Figure~\ref{fig:genpos}. 
	\end{example}

	\begin{figure}[t]
		\centering
		\includestandalone[width=0.6\linewidth]{figures/gen_pos}
		\caption{Bisectors of two sites in $\torus{3}$: general position vs.\ non-general position.}
		\label{fig:genpos}
	\end{figure}
	
	If $S$ is not in general position, the Voronoi regions might not be pure dimensional; see Example~\ref{exmp:lattice} below.
	This happens because the closure of the interior of a Voronoi region might be a proper subset of the region.
	However, for $S$ in general position, this situation does not occur.
	
	\begin{lemma}\label{lem:puredim}
		If $S\subset\cH$ is a discrete set in general position, then any Voronoi region $\VR_S(a)$ agrees with the closure of its interior.
	\end{lemma}
	
	\begin{proof}
		Let $x\in\VR_S(a)$ and $x^{(t)}=a+t(x-a)$ for $t\in[0,1)$.
		Consider also an arbitrary site $b\in S\setminus\{a\}$.
		Due to the general position of $S$, we have
		\[ \max_{i\in I(a,b)}(x_i-a_i) \ \leq \ \max_{j\in I(b,a)}(x_j-b_j) \enspace ,\]
		where $I(a,b):=\smallSetOf{i\in[n]}{a_i<b_i}$ as $x\in h(a,b)$.
		Then
		\[\begin{split}
			\max_{i\in I(a,b)}\left(x^{(t)}_i-a_i\right) \ &= \ t\max_{i\in I(a,b)}(x_i-a_i)\\
			& \leq \ t\max_{j\in I(b,a)}(x_j-b_j) \ = \ \max_{j\in I(b,a)}t(x_j-b_j)\\
			& < \ \max_{j\in I(b,a)}\left((1-t)(a_j-b_j)+t(x_j-b_j)\right)\ = \ \max_{j\in I(b,a)}\left(x^{(t)}_j-b_j\right) \enspace .
		\end{split}
		\]
		As $S$ is discrete, the interior of $\VR_S(a)$ is the intersection of the interiors of the halfspaces $h(a,b)$ for $b\neq a$.
		So the previous inequality shows that $x^{(t)}$ belongs to the interior of $\VR_S(a)$ for every $t\in[0,1)$.
		The conclusion follows because ${\lim_{t\to 1}x^{(t)}=x}$.
	\end{proof}
	
	\begin{remark}\label{rem:switch}
		In the definition (\ref{eq:defVR}) of Voronoi regions we put the sites into the second position: the points whose distance \emph{to} the site is minimal are selected.
		If we switch the position, \ie the defining inequalities become $d_\triangle(a,x)\leq d_\triangle(b,x)$, then our Voronoi regions become \emph{$\min$-tropically convex}.
		In that case, the focus lies on the minimal distance \emph{from} a site.
		
		Replacing $\max$ by $\min$ and $-\infty$ by $\infty$ we arrive at the \emph{$\min$-tropical semiring}, which is isomorphic to $\TT$ as a semiring under the map $x\mapsto -x$; see \cite[\textsection 1.3]{ETC}.
		The change from $\max$-tropical convexity to $\min$-tropical convexity from switching the order of the arguments in the distance function can be seen now from the relation: $d_\triangle(a,x)=d_\triangle(-x,-a)$.
	\end{remark}
	
	\section{Super-discrete sets of sites}

	We continue the study of a possibly infinite number of sites, assuming discreteness throughout.
	In Example~\ref{ex:nonpolyh} we saw that tropical Voronoi regions do not need to be tropical polyhedra in general.
	Nonetheless, tropical Voronoi regions are always locally polyhedral.
	Here we will explore the details, and we will develop a notion which forces tropical polyhedrality.
	This turns out to be applicable to tropical Voronoi diagrams of lattices.
	A subset of $\cH$ is a \emph{tropical quasi-polyhedron} if its intersection with any bounded tropical polyhedron is a tropical polyhedron.
	
	\begin{proposition}\label{prop:trop-quasi}
		The tropical Voronoi regions of a discrete set $S\subset\cH$ are tropical quasi-polyhedra.
	\end{proposition}
	
	\begin{proof}
		Up to a translation, we can assume that $\0$ is among the sites $S$.
		It suffices to show that $\VR_S(\0)$ intersected with any symmetric tropical ball around $\0$ is a tropical polyhedron.
		For $M\in\RR_{>0}$ let $B_M$ the symmetric tropical ball given by $x_i-x_j\leq M$ for all $i,j\in[n]$.
		Due to the discreteness of $S$ there are only finitely many points of $S$ inside the cube $C_M = [-(n-1)M,(n-1)M]^n$.
		
		Consider $a\in S$ which lies outside $C_M\cap\cH$.
		Then there exists $i\in [n]$ with $|a_i|>{(n-1)M}$.
		We claim that there is an index $j\in[n]$ such that $a_j < -M$.
		To see this, assume the contrary.
		Then $\sum_{k\in[n]}a_k=a_i+\sum_{k\neq i}a_k>(n-1)M+{(n-1)\cdot(-M)}=0$, which contradicts $a\in\cH$.
		
		Let $x\in B_M$.
		Then $\max_{k\in[n]}(-a_k+x_k)\geq -a_j+x_j>M+x_j\geq\max_{k\in [n]}x_k$.
		This yields $B_M\subseteq h(\0,a)$.
		Therefore, $\VR_S(\0)\cap B_M=\bigcap_{s\in C_M\cap(S\setminus\{\0\})}h(\0,s)\cap B_M$ is a bounded intersection of finitely many tropical halfspaces, \ie a tropical polyhedron.
	\end{proof}
	
	Bounded tropical quasi-polyhedra are tropical polyhedra.
	This gives us a first sufficient criterion for a Voronoi region to be a tropical polyhedron.
	
	\begin{corollary}
		If $S$ is a discrete set and $\VR_S(s)$ is bounded for some $s\in S$, then $\VR_S(s)$ is a tropical polyhedron.
	\end{corollary}
	
	For the symmetric tropical distance function the situation is considerably more complicated.
	For instance, by \cite[Theorem~6]{TropBis}, the symmetric tropical Voronoi regions of finitely many sites are a star convex union of a certain class of ordinary convex polytopes.
	In general, these regions are not tropically convex.
	
	Next we describe a class of (finite or infinite) sets with nice Voronoi regions.
	\begin{definition}
		Let $r,R\in\RR\cup\{\infty\}$ such that $0<r<R$.
		A set $S\subset\cH$ is called an \emph{$(r,R)$-system} if $(s+r\triangle)\cap S=\{s\}$ for all $s\in S$ and $(x+R\triangle)\cap S\neq\emptyset$ for all $x\in\cH$.
	\end{definition}
	For $R=\infty$, we consider $R\triangle=\cH$, so an $(r,\infty)$-system imposes only a uniform lower bound on the distances between sites.
	When $R$ is finite, the above definition agrees with \cite[Definition 3.1.4]{Voigt:2008} despite being formally different.
	In that case, our version is equivalent because the asymmetric tropical distance is strongly equivalent to the Euclidean distance (\ie there exist $\alpha,\beta>0$ such that $\alpha d_{L^2}(x,y)\leq d_{\triangle}(x,y)\leq \beta d_{L^2}(x,y)$ for all $x,y\in\cH$, where $d_{L^2}$ is the Euclidean distance).
	Occasionally, $(r,R)$-systems are also called \enquote{Delone sets} in the literature; \eg see \cite[loc.\ cit.]{Voigt:2008}.
	Here we prefer the slightly more sterile terminology to avoid a confusion with the Delone complexes to be discussed in Section~\ref{sec:delaunay} below.
	The following generalizes \cite[Lemma~4.6]{RRlattice}.
	\begin{lemma}\label{lem:compact}
		For $R<\infty$ the tropical Voronoi regions of $(r,R)$-systems are bounded and thus compact.
	\end{lemma}
	
	\begin{proof}
		Let $S$ be an $(r,R)$-system in $\cH$ and $s\in S$.
		Up to translation, we can assume that $s=\0$.
		Select $i\in[n]$ arbitrary and consider the cone $C_i$ given by the equations $x_i \leq 0$ and $x_j > 0$ for all $j\neq i$.
		Since $C_i$ is a full-dimensional convex cone, one can find $x\in C_i$ such that $x+R\triangle\subset C_i$.
		Then there exists $t\in S\cap(x+R\triangle)$ because $S$ is an $(r,R)$-system.
		In particular, $t$ is a site contained in~$C_i$.
		
		The equation of the tropical halfspace $h(\0,t)$ is $\max_{j\neq i}x_j\leq x_i-t_i$. From the fact that $\sum_{j\neq i}x_j=-x_i$, we obtain $-\frac{1}{n-1}x_i\leq\max_{j\neq i}x_j\leq x_i-t_i$ and thus $x_i\geq\frac{n-1}{n}t_i$ for every $x\in h(\0,t)$.
		This restricts, particularly, to points of $\VR_S(\0)$, which is a subset of $h(\0,t)$.
		
		We have shown that, for an arbitrary $i\in[n]$, the $i$th coordinate $x_i$ is bounded uniformly from below for every $x\in\VR_S(\0)$.
		In other words, there exists $\delta>0$ such that for every $x\in\VR_S(\0)$ and $i\in [n]$ we have $x_i\geq -\delta$.
		Using again the property $\sum x_i=0$, we also obtain $x_i\leq(n-1)\delta$ for all $x\in\VR_S(\0)$ and $i\in [n]$.
		
		Summing up, $\VR_S(\0)$ is a subset of the cube $[-\delta,(n-1)\delta]^n$, so it is bounded.
	\end{proof}
	
	Because every ball of radius $R$ contains a point of any $(r,R)$-system, such sets are necessarily infinite if $R$ is finite.
	Thus, these form a quite restricted class of sets, whereas the analysis in \cite{Voigt:2008} admits arbitrary unbounded polyhedral Euclidean Voronoi regions for discrete sets.
	We now describe a class of sets whose tropical Voronoi regions are always tropical polyhedra, even when they are unbounded.
	To this end we need to introduce some notation.
	For a subset $I$ of $[n]$ we consider the projection $\pi_I:\RR^n\rightarrow\RR^{|I|}$ mapping a point $x$ to $(x_i)_{i\in I}$, its entries with coordinates in $I$.
	
	\begin{definition}\label{def:super-discrete}
		We call a set $S\subset\cH$ \emph{super-discrete} if for every $i\in[n]$ the projection~$\pi_i(S)$ is a discrete subset of $\RR$. 
	\end{definition}
	
	A super-discrete set is, in particular, a discrete subset of $\cH$.
	To see this, notice that every cube $[m,M]^n$ intersected with $\cH$ contains finitely many points of a super-discrete set; the final assertion can be shown inductively.
	Examples of super-discrete sets include finite sets and rational lattices.
	For irrational lattices it may happen that a projection onto one coordinate is dense in $\RR$; see Example~\ref{exmp:irr} below.
	The set in Example~\ref{ex:nonpolyh} is discrete but not super-discrete: the projection onto the second coordinate is not a discrete set.
	
	To the best of our knowledge, the notion of super-discreteness has not been considered before.
	It is similar in spirit to $(r,R)$-systems, but there are important differences, as the subsequent examples show.
	The concept makes sense in general, but it is particularly natural in the tropical setting; see Theorem~\ref{th:polySuperDisc} below.
	\begin{example}\label{exmp:ln}
		The sequence of sites $s_i=(\ln(i),-\ln(i))$ for $i\in\ZZ_{>0}$ forms a super-discrete set in $\torus{2}$, but $d_\triangle(s_i,s_{i+1})=2\ln((i+1)/i)$ tends to zero as $i$ goes to infinity.
		So it is not an $(r,R)$-system for any $0<r<R$.
	\end{example}
	
	\begin{example}\label{exmp:irr}
		Let $L$ be the lattice generated by $(1,1,-2)$ and $(0,\sqrt{2},-\sqrt{2})$, which is not rational.
		Then $\pi_2(L)=\SetOf{\alpha+\beta\sqrt{2}}{\alpha,\beta\in\ZZ}$ is dense in $\RR$ by Kronecker's density theorem \cite[Chapter~XXIII]{HardyWright:2008}.
		Hence, $L$ is not super-discrete; yet it is an $(r,R)$-system.
	\end{example}
	
	\begin{remark} \label{rmk:super-discrete}
		By definition, subsets of super-discrete sets are also super-discrete.
		Moreover, any projection $\pi_I(S)$ of a super-discrete set $S$ is super-discrete.
	\end{remark}
	
	An element $x$ of a set $G\subseteq\RR^n$ is called \emph{nondominated} if there is no $y\in G\setminus\{x\}$ such that $x\leq y$.
	This notion appears in multicriteria optimization \cite{Ehrgott:2005}; see also \cite{MonCon} and \cite{Loho+Smith:2019} for connections to tropical combinatorics.
	
	\begin{lemma} \label{lemma:supdisc-fingen}
		Let $G$ be a super-discrete subset of $\RR^n_{\geq 0}$.
		Then there are finitely many nondominated points in $G$.
	\end{lemma}
	
	\begin{proof}
		For all $i\in[n]$ the sets $\pi_i(G)$ are discrete subsets of of $\RR_{\geq 0}$ and thus countable and well-ordered.
		Hence, we can pick an order-preserving embedding $\rho_i:\pi_i(G)\rightarrow\ZZ_{>0}$ for every $i\in[n]$.
		
		Therefore, the map $\rho:G\rightarrow\ZZ_{>0}^n$, $x\mapsto(\rho_1(\pi_1(x)),\dots,\rho_n(\pi_n(x)))$ is injective and order-preserving.
		In particular, we have a bijection between the nondominated points of $G$ and the nondominated points of $\rho(G)$.
		But $\rho(G)$ has finitely many nondominated points by Dickson's lemma \cite[Theorem 2.1.1]{HerzogHibi:2011}.
	\end{proof}
	
	Dickson's lemma has a prominent role in commutative algebra.
	That it occurs here is not a coincidence; see Section~\ref{sec:delaunay} below.
	For now, we are content with the following combinatorial result.
	
	\begin{theorem} \label{th:polySuperDisc}
		If $S$ is a super-discrete subset of $\cH$, then all the cells of the Voronoi diagram $\VD(S)$ are tropical polyhedra.
	\end{theorem}
	
	\begin{proof}
		Let $s\in S$ be arbitrary.
		After a translation, we can assume that $s=\0$.
		We prove that $\VR_{S}(\0)$ is a tropical polyhedron by showing that there exists a finite subset~$T$ of $S\setminus\{\0\}$ such that $\VR_{S}(\0)=\bigcap_{t\in T}h(\0,t)$.
		
		Consider the hyperplane arrangement $\SetOf{x_i=0}{i\in [n]}$ in $\cH$.
		Its maximal cells are in bijection with the $2^n-2$ ordered partitions of $[n]$ in two nonempty sets.
		A partition $I\sqcup J=[n]$ corresponds to the \enquote{half-open} cone given by the hyperplanes $x_i > 0$ for~$i\in I$ and $x_j\leq 0$ for $j\in J$.
		We call $(I,J)$ the signature of the cone.
		
		Denote by $S_{I,J}$ the points of $S\setminus\{\0\}$ that are contained in the cone with signature~$(I,J)$.
		For a point $a\in S_{I,J}$, the halfspace $h(\0,a)$ is given by the equation $\max_{i\in I}x_i\leq\max_{j\in J}(-a_j+x_j)$.
		
		Let $b\in S_{I,J}$ such that $-\pi_J(b)\geq -\pi_J(a)$.
		Then we have $\max_{j\in J}(-a_j+x_j)\leq\max_{j\in J}(-b_j+x_j)$ for every $x\in\cH$.
		This implies the inclusion $h(\0,a)\subseteq h(\0,b)$.
		In this case, $h(\0,b)$ does not contribute to the intersection $\bigcap_{s\in S\setminus\{\0\}}h(\0,s)$.
		Therefore, the significant halfspaces come from the nondominated points of $-\pi_J(S_{I,J})$.
		By Lemma~\ref{lemma:supdisc-fingen}, there are only finitely many nondominated points, as $\pi_J(S_{I,J})$ is also super-discrete; we used Remark~\ref{rmk:super-discrete}.
		
		There could be infinitely many points that project onto a nondominated point of~$-\pi_J(S_{I,J})$, but all of them give the same halfspace.
		Indeed, from the above observations, $h(\0,a)=h(\0,b)$ is equivalent to $\pi_J(a)=\pi_J(b)$ for points $a,b\in S_{I,J}$.
		Hence, we can select a finite subset $T_{I,J}$ of $S_{I,J}$ such that $\bigcap_{t\in T_{I,J}}h(\0,t)=\bigcap_{s\in S_{I,J}}h(\0,s)$.
		
		All in all, we have $\VR_S(\0)=\bigcap_{\emptyset\neq I\subset [n]}\bigcap_{t\in T_{I,[n]\setminus I}}h(\0,t)$, which is an intersection of finitely many tropical halfspaces.
	\end{proof}
	
	\begin{remark}
		The proof of the above theorem gives a way to compute Voronoi regions: by looking at nondominated points in certain cones around each site.
		If $S$ is a rational lattice, then we have to deal with multiple multi-objective integer programs~\cite[\textsection 8.3]{Ehrgott:2005}.
		To see this, one can fix a basis $b_1,\dots,b_k$ of $S$ and search for nondominated points of the form $x=y_1b_1+\dots+y_kb_k$ with ${y_1,\dots,y_k\in\ZZ}$ and $x$ belonging to a cone~$C_{I,J}$.
		Then the set of feasible coefficients $y$ represents the set of integer points in a polyhedron and the objectives will be also linear functionals in $y$.
		
		However, the proof of Lemma~\ref{lem:compact} shows that, for $(r,R)$-systems, one can reduce the search by finding a bounded set containing the Voronoi region.
		Even with this information, the procedure might be time consuming, as there could be exponentially many Voronoi relevant vectors; \cf \cite{BloemerKohn:2018}.
	\end{remark}
	
	We close this section with examples of asymmetric tropical Voronoi diagrams for a family of lattices.
	These are interesting for several reasons; \eg they provide counter-examples to several claims made in \cite{RRlattice}.
	
	\begin{figure}[t]
		\centering
		\includestandalone[width=.75\linewidth]{figures/OtherLattice2}
		\caption{The Voronoi region $\VR(\0)$ in the lattice $L_2(2,1,1)$.
			The parts in a darker shade of orange are also contained in the Voronoi regions of $b_0+b_1=(1,0,-1)$ and $-b_0-b_1=(-1,0,1)$, respectively.
			The six blue points are the tropical vertices of $\VR(\0)$.}
		\label{fig:RRlattice-counterexample}
	\end{figure}
	
	\begin{example} \label{exmp:lattice}
		In \cite[\textsection 6.4]{RRlattice}, the authors construct a lattice $L_2(\alpha,\gamma,\eta)$ in $\cH\subset\RR^3$ with basis $b_0=(\alpha,-\alpha,0)$ and $b_1=(-\gamma,\gamma+\eta,-\eta)$.
		Here the three parameters $\alpha,\gamma,\eta$ are positive integers with $\gamma<\alpha\leq\gamma+\eta$.
		We will show that the lattice $L_2(\alpha,\gamma,\eta)$ is graphical if $\alpha$ divides $\gamma+\eta$.
		To this end consider the $3{\times}3$-matrix
		\[
		Q \ = \ \begin{bmatrix}
			\alpha+\eta & -\alpha & -\eta \\
			-\alpha & \alpha & 0 \\
			-\eta & 0 & \eta
		\end{bmatrix} \enspace ,
		\]
		which is the Laplacian matrix of a multi-tree on three nodes; the first node is adjacent to the other two, with multiplicities $\alpha$ and $\eta$.
		We compute $(\alpha+\eta,-\alpha,-\eta)=\left(1+\frac{\gamma+\eta}{\alpha}\right)b_0+b_1$ and $(-\alpha,\alpha,0)=-b_0$.
		That invertible linear transformation of the basis is unimodular when $\alpha$ divides $\gamma+\eta$.
		So this furnishes a counter-example to~\cite[Proposition~6.29]{RRlattice}, where it was claimed that $L_2(\alpha,\gamma,\eta)$ is not graphical.
		Observe that~$\gamma$ does not occur in the matrix $Q$.
		
		Figure~\ref{fig:RRlattice-counterexample} displays the lattice $L_2(2,1,1)$ and the Voronoi region of the origin.
		The latter is the $\max$-tropical polytope with the six tropical vertices
		\begin{equation}\label{eq:RRlattice-counterexample:vertices}
			(1,-1,0) \,,\ \underline{(1,1,-2)}\,,\ \underline{(0,1,-1)}\,,\ (-1,1,0)\,,\ (-2,1,1)\,,\ (0,-1,1) \enspace ,
		\end{equation}
		in cyclic order.
		These are the local maxima of the distance function to the closest site (called \enquote{critical points} in \cite{RRlattice}) that are contained in $\VR(\0)$.
		The underlined tropical vertices do not occur in \cite[Lemma~6.19]{RRlattice} as they do not appear via the perturbation suggested in \cite[\textsection 6.1.2]{RRlattice}.
		Consequently, these local maxima are also missing in \cite[Theorem~6.9~(ii)]{RRlattice}.
		
		Moreover, the reflection of the tropical vertices at $\0$ is not a translation of themselves, whence that lattice is not strongly reflection invariant.
		This refutes \cite[Theorem~6.1]{RRlattice}.
		The same example also disproves \cite[Theorem~6.28]{RRlattice}:  the lattice $L_2(2,1,1)$ is defined by a multi-tree on three vertices, but it is not strongly reflection invariant.
		Notice that \cite[Theorem~6.9 (ii)]{RRlattice} is also used in the proof of \cite[Theorem~4]{LapLatticeGraph}.
		Omid Amini pointed out to us that the weak reflection invariance in \cite[Theorem~6.1]{RRlattice} and thus also the proof of the Riemann--Roch Theorem for Laplacian lattices of connected graphs, \cite[Corollary~6.2]{RRlattice}, remain valid.
	\end{example}
	
	\section{Power diagrams over fields of Puiseux series}
	\label{sec:power}

	Our next goal is to relate asymmetric tropical Voronoi diagrams with the ordinary polyhedral geometry over ordered fields.
	To this end, we consider the field of generalized dual Puiseux series $\hahnseries{\RR}{t}^*$.
	Its elements are the formal power series in $t$, with real coefficients, such that the exponents form a strictly decreasing sequence of reals without finite accumulation points.
	That field is ordered, and it is equipped with the dual valuation map
	\[
	\val^* : \hahnseries{\RR}{t}^* \to \RR \,,\ \ \sum_{k=0}^\infty \alpha_k t^{r_k} \mapsto r_0 \enspace,
	\]
	where $\alpha_0\neq 0$ and $r_0>r_1>\cdots$, which sends a generalized dual Puiseux series to its highest exponent.
	The sign of the generalized Puiseux series $\sum \alpha_k t^{r_k}$ is the sign of the leading coefficient $\alpha_0$; hence, nonnegative Puiseux series are those with $\alpha_0\geq 0$.
	The map $\val^*$ is surjective onto the reals, and it preserves the ordering, if restricted to nonnegative generalized dual Puiseux series:
	\[
	\val^*(\bm x) \leq \val^*(\bm y) \quad \text{if and only if} \quad \bm x \leq \bm y
	\]
	for every $\bm x, \bm y\in\hahnseries{\RR}{t}^*_{\geq 0}$.
	Notice that the ordinary Puiseux series with real coefficients have rational exponents, which are rising instead of falling, and the usual valuation map reverses the order, since it picks the lowest degree.
	The compatibility with the order relations makes the generalized dual Puiseux series more convenient for our purposes.
	In the sequel, we abbreviate $\KK=\hahnseries{\RR}{t}^*$.
	We use the term \enquote{dual} for our Puiseux series to stress that we employ decreasing exponents; see \cite[\textsection 2.7]{ETC}.
	
	To discuss power diagrams in $\KK^n$ we need to define a way to measure distances on vectors of generalized Puiseux series.
	To this end, we consider the map
	\[
	\|\cdot\|:\KK^n \to \KK_{\geq 0} \,,\ \bm x \mapsto \sqrt{\sum_{i\in[n]} \bm x_i^2} \enspace ,
	\]
	which is called the \enquote{Euclidean norm} in \cite[p. 83]{BasuPollackRoy:2006}.
	It is well defined because the generalized dual Puiseux series form a real closed field \cite{Markwig:2010}.
	Yet, this is not a norm on the infinite-dimensional real vector space $\KK^n=(\hahnseries{\RR}{t}^*)^n$ in the usual sense, as its values are not real numbers.
	
	Pick a finite set of sites $\bm S\subset \KK^n$ and an arbitrary \emph{weight function} $w:\bm S\to\KK_{\geq 0}$.
	Then we obtain the \emph{farthest power region} of $\bm a\in\bm S$, with respect to $w$, which is the set
	\[
	\PR_{\bm S}^w(\bm a) \ := \ \bigSetOf{\bm x\in\KK_{\geq 0}^n}{\|\bm x-\bm a\|^2-w(\bm a) \geq \|\bm x-\bm b\|^2-w(\bm b) \text{ for all } \bm b\in \bm S} \enspace ,
	\]
	The \emph{farthest power diagram} of $\bm S$ with respect to $w$ is the set of all intersections of the farthest power regions of $\bm S$, partially ordered by inclusion.
	We denote it $\PD(S)$.
	Farthest power diagrams are also called \enquote{maximal power diagrams} \cite[\textsection 3]{PowDiag}.
	The computational aspects of power diagrams can be traced to an article of Imai, Iri and Murota \cite{IIM:1985}.
	In the context of sphere packings, power diagrams were previously studying under the name \enquote{generalized Dirichlet cells} in a book by Fejes T\'{o}th \cite[p.~199]{FejesToth:1964}.
	The farthest power diagram occurs in algorithms involving intersections of balls~\cite{Aurenhammer:1988}.
	A more comprehensive historical account can be found in the introduction of the article on power diagrams by Aurenhammer \cite{PowDiag}.
	
	We abbreviate $\bm h^w(\bm a,\bm b)=\PR_{\{\bm a,\bm b\}}^w(\bm a)$.
	Occasionally, we will also call the intersection $\bisector(\bm a,\bm b)=\bm h^w(\bm a,\bm b)\cap\bm h^w(\bm b, \bm a)$ a \emph{(two point) bisector}.
	\begin{proposition}\label{prop:power-region}
		For the special weight function $w(\bm a)=\|\bm a\|^2$ the farthest power region $\bm h^w(\bm a,\bm b)$ for two sites is a linear halfspace in $\KK^n$.
		Consequently, for an arbitrary finite set of sites, $\bm S$, the power region $\PR_{\bm S}^w(\bm a)$ is a polyhedral cone.
	\end{proposition}
	\begin{proof}
		We have $\|\bm x-\bm a\|^2-\|\bm a\|^2 = \|\bm x\|^2-2\sum_{i\in[n]}\bm x_i \bm a_i$, whence the inequality $\|{\bm x-\bm a}\|^2-w(\bm a) \geq \|{\bm x-\bm b}\|^2-w(\bm b)$ is equivalent to $\sum_{i\in[n]}\bm a_i \bm x_i \leq \sum_{i\in[n]}\bm b_i \bm x_i$.
		For general $\bm S$ the power region is then described by finitely many homogeneous linear inequalities.
	\end{proof}
	Observe that the proof above only exploits the fact that $\|\cdot\|^2$ is a quadratic form.
	The real-closedness of the field $\KK$ is irrelevant here.
	In our notation for power diagrams, we usually omit the upper index \enquote{$w$} when $w=\|\cdot\|^2$.
	
	To see $d_\triangle$ as a distance function requires passing from $\RR^n$ to the quotient $\torus{n}$.
	Yet, here we want to work in a tropically inhomogeneous setting.
	This will allow us to state our first main result in a particularly concise form.
	In $\KK^n$ we consider
	\[
	\bm \cH \ := \bigSetOf{\bm x\in\KK_{>0}^n}{ \bm x_1 \bm x_2\cdots \bm x_n = 1 } \enspace ,
	\]
	which is the intersection of an affine algebraic hypersurface over $\KK$ with the positive orthant.
	In differential geometry, the hypersurface $\bm\cH$ occurs as a hyperbolic affine hypersphere \cite[Example~3.1]{AffDiffGeomHypsurf}.
	This tropicalizes to the tropical hypersurface $\val^*(\bm \cH)=\cH$.
	Further, the ray $\KK_{\geq 0} \cdot \bm x$, for $\bm x\in\KK_{> 0}^n$, intersects $\bm\cH$ in a unique point.
	We obtain a commutative diagram, where the horizontal maps are embeddings and canonical projections, respectively:
	\[
	\begin{tikzcd}
		\bm\cH \ar[r, hook] \ar[d, "\val^*"] & \KK_{>0}^n \ar[r, twoheadrightarrow] \ar[d, "\val^*"] & \KK_{>0}^n/\KK_{>0} \ar[d, "\val^*"]  \\
		\cH \ar[r, hook] & \RR^n \ar[r, twoheadrightarrow] & \torus{n}
	\end{tikzcd}
	\]
	
	\begin{lemma} \label{lemma:polyPR}
		Let $S\subset\cH$ be a super-discrete set of sites in general position, and let $\bm S\subset\bm\cH$ be a lifted point configuration such that $\val^*:\bm S\to -S$ is bijective.
		Then the cells of $\PD(\bm S)$ are polyhedral.
	\end{lemma}
	
	\begin{proof}
		Consider $I\sqcup J=[n]$ an ordered partition of $[n]$ and $C_{I,J}$ the open polyhedron given by the equations $x_i>s_i$ for $i\in I$ and $x_j<s_j$ for $j\in J$. The set $-\pi_J(C_{I,J}\cap S)$ has finitely many nondominated points due to $S$ being super-discrete and Lemma \ref{lemma:supdisc-fingen}.
		We denote by $S_{I,J}$ the set of points in $C_{I,J}\cap S$ that project to the nondominated points of $-\pi_J(C_{I,J}\cap S)$.
		By general position, no two points project onto the same nondominated point, so $S_{I,J}$ is finite.
		
		Let $T$ be the union of all the sets $S_{I,J}$ over all ordered partitions $I\sqcup J=[n]$.
		The set $T$ is finite and contains all the Voronoi neighbors of $s$, due to general position.
		The last condition implies
		\[\VR_S(s) \ = \ \bigcap_{t\in T}h(s,t) \enspace.\]
		
		Consider an arbitrary site $u$ from $S\setminus(T\cup\{s\})$ and $\bm u\in\bm S$ such that $\val^*(\bm u)=-u$.
		We show that
		\[ \bigcap_{\bm t\in\bm S\cap(\val^*)^{-1}(-T)}\bm h(\bm s, \bm t) \ \subseteq \ \bm h(\bm s, \bm u) \enspace, \]
		which will imply that $\PR_{\bm S}(\bm s)$ is a polyhedral cone with hyperplane description given by
		\[ \PR_{\bm S}(\bm s) \ = \ \bigcap_{\bm t\in\bm S\cap(\val^*)^{-1}(-T)}\bm h(\bm s, \bm t) \enspace . \]
		
		Let $K:=\smallSetOf{i\in [n]}{u_i>s_i}$ and $L:=\smallSetOf{j\in [n]}{u_j<s_j}$.
		By the construction of~$T$, there exists $t\in T\cap C_{K,L}$ such that~$t_j>u_j$ for all $j\in L$.
		Pick $\bm t\in\bm S$ such that~$\val^*(\bm t)=-t$.
		
		Let $\bm x\in\bm h(\bm s, \bm t)$ arbitrary.
		This is a point satisfying $\sum_{i\in K}(\bm s_i-\bm t_i)\cdot\bm x_i\leq{\sum_{j\in L}(\bm t_j-\bm s_j)\cdot\bm x_j}$.
		In the following expression, we use the notation $x=\val^*(\bm x)$.
		Since $u\in C_{K,L}$ we obtain the equalities
		\begin{equation}\label{eq:val1}
			\val^*\left(\sum_{i\in K}(\bm s_i-\bm u_i)\cdot\bm x_i\right) \ = \ \max_{i\in K}(-s_i+x_i)
		\end{equation}
		and
		\begin{equation}\label{eq:val2}
			\val^*\left(\sum_{j\in L}(\bm u_j-\bm s_j)\cdot\bm x_j\right) \ = \ \max_{j\in L}(-u_j+x_j) \enspace.
		\end{equation}
		But $\bm x\in\bm h(\bm s, \bm t)$ implies $\max_{i\in K}(-s_i+x_i)\leq\max_{j\in L}(-t_j+x_j)$.
		The latter is strictly smaller than $\max_{j\in L}(-u_j+x_j)$ in view of our selection for $t$.
		This entails $\max_{i\in K}(-s_i+x_i)<\max_{j\in L}(-u_j+x_j)$. Using the last inequality with (\ref{eq:val1}) and (\ref{eq:val2}), we obtain
		\[\sum_{i\in K}(\bm s_i-\bm u_i)\cdot\bm x_i \ < \ \sum_{j\in L}(\bm u_j-\bm s_j)\cdot\bm x_j \enspace .\]
		
		The choice of $\bm x$ was arbitrary, so $\bm h(\bm s, \bm t)\subseteq\bm h(\bm s, \bm u)$.
		Consequently,
		\[\bigcap_{\bm t'\in\bm S\cap(\val^*)^{-1}(-T)}\bm h(\bm s, \bm t') \ \subseteq \ \bm h(\bm s, \bm u) \enspace .\]
	\end{proof}
	
	In the following main result, the assumption on general position allows arbitrary lifts for the sites.
	This is similar to the relationship between tropical and Puiseux polyhedra; \eg see \cite{DevelinYu07}, \cite[\S2]{ABGJ:SIREV} and \cite[Corollary 8.15]{ETC}.
	\begin{theorem} \label{th:PuiseuxLift}
		Let $S\subset\cH$ be a nonempty super-discrete set of sites in general position.
		Further, let $\bm S\subset\bm\cH$ be a lifted point configuration such that $\val^*:\bm S\to -S$ is bijective.
		Then $\val^*$ maps each farthest power region onto the corresponding Voronoi region, and this induces a poset isomorphism from the farthest power diagram $\PD(\bm S)$ to the asymmetric tropical Voronoi diagram $\VD(S)$.
	\end{theorem}
	\begin{proof}
		Pick a lifted point configuration $\bm S$ on the hypersurface $\bm\cH$, \ie $\val^*(\bm S)=-S$; recall that $-\cH=\cH$.
		For $\bm a, \bm b \in \bm S$, by Proposition~\ref{prop:power-region}, the power region $\bm h(\bm a,\bm b)$ is determined by the linear inequality
		\begin{equation}\label{eq:PR-pair:ineq}
			\sum_{i\in[n]}\bm a_i \bm x_i \ \leq \ \sum_{i\in[n]}\bm b_i \bm x_i \enspace . 
		\end{equation}
		As $\bm a,\bm b \in \bm \cH$, the tropicalization of \eqref{eq:PR-pair:ineq} reads
		\begin{equation}
			\bigoplus_{i\in[n]}(-a_i + x_i) \ \leq \ \bigoplus_{i\in[n]} (-b_i + x_i) \enspace ,
		\end{equation}
		which is the defining inequality for $h(a,b)$.
		This yields $\val^*(\bm h(\bm a,\bm b))=h(a,b)$.
		
		The proof of Lemma~\ref{lemma:polyPR} implies that there is a finite subset $\bm S_a\subseteq\bm S\setminus\{\bm a\}$ such that $\PR(\bm a)=\bigcap_{\bm b\in\bm S_a}\bm h^w(\bm a,\bm b)$ and $\VR(a)=\bigcap_{b\in S_a} h(a,b)$, where $-S_a=\val^*(\bm S_a)$.
		Moreover, we have:
		\begin{equation}\label{eq:inclusion}
			\val^*(\PR(\bm a)) \ \subseteq \ \bigcap_{\bm b\in\bm S_a}\val^*(\bm h(\bm a,\bm b)) \ = \ \bigcap_{b\in S_a}h(a,b) \ = \ \VR(a) \enspace .
		\end{equation}
		It remains to show the reverse inclusion, which hinges on the following key concept in tropical convexity.
		A pair of square matrices $(X^-,X^+)$ in $\TT^{n\times n}$ is \emph{tropically sign singular} if $X^-$ and $X^+$ support a pair of perfect matchings which can be combined into a directed graph on $n+n$ nodes such that those matchings certify the equality $\tdet X^-=\tdet (X^-\oplus X^+)=\tdet X^+$ of tropical determinants; see \cite[\S7.6]{ETC}.
		Recall that computing a tropical determinant of a matrix $X\in\TT^{n\times n}$ is equivalent to finding a perfect matching of maximal value in the bipartite graph on $n+n$ nodes which corresponds to the nonvanishing coefficients of $X$; see \cite[Corollary 3.12]{ETC}.
		Now, a pair of matrices ${(A^-,A^+)\in\TT^{m\times n}}$ is \emph{tropically sign generic} if it does not contain a tropically sign singular square submatrix.
		Tropical sign genericity is the relevant concept of general position for tropical linear inequalities, which allows to translate between Puiseux polyhedra and their tropicalizations.
		Specifically, by \cite[Theorem~8.12]{ETC}, equality in~\eqref{eq:inclusion} follows, if we can show that the pair of matrices defining $\VR(a)$ is tropically sign generic.
		
		For two distinct sites $a$ and $b$ we consider $I(a,b):=\smallSetOf{k\in[n]}{a_k<b_k}$.
		General position of the sites then implies $I(b,a)=[n]\setminus I(a,b)$.
		The pair of matrices ${(A^-,A^+)\in\TT^{S_a\times[n]}}$ which describes $\VR(a)$ as a tropical polyhedron has the entries
		\begin{align*}
			A^{-}_{b,k} \ &= \ 
			\begin{cases}
				-a_k & \text{if }k\in I(a,b) \\
				-\infty & \text{if }k\in I(b,a)
			\end{cases} \\
			\intertext{and}
			A^{+}_{b,k} \ &= \
			\begin{cases}
				-\infty & \text{if }k\in I(a,b) \\
				-b_k & \text{if }k\in I(b,a) \enspace .
			\end{cases} 
		\end{align*}
		The matrix $A:=A^-\oplus A^+$ has finite entries due to general position.
		Suppose that the pair $(A^-,A^+)$ is tropically sign singular.
		Then there exists a nonempty set $B\subseteq S_a$ and another set $K\subseteq [n]$ such that $|B|=|K|$ and $\tdet A^-_{B,K}=\tdet A^+_{B,K}=\tdet A_{B,K}$.
		This is equivalent to the existence of bijections $\mu,\nu:B\rightarrow K$ with $\mu(b)\in I(a,b)$ and $\nu(b)\in I(b,a)$, for $b\in J$, as well as
		\begin{equation}\label{eq:st}
			-\sum_{b\in B}a_{\mu(b)} \ = \ \tdet A \ = \ -\sum_{b\in B}b_{\nu(b)} \enspace .
		\end{equation}
		However, we have $\sum_{b\in B}b_{\nu(b)}<\sum_{b\in B}a_{\nu(b)}=\sum_{k\in K}a_{k}=\sum_{b\in B}a_{\mu(b)}$, where the inequality comes from $\nu(j)\in I(b,a)$, and the two equalities use that $\mu$ and $\nu$ are bijections.
		We arrive at a contradiction, which refutes \eqref{eq:st}.
		Hence, $(A^-,A^+)$ is tropically sign generic, yielding equality in~\eqref{eq:inclusion}.
	\end{proof}
	
	\begin{figure}[t]
		\resizebox{1.0\textwidth}{!}{
		\begin{tabular}{ccc}
			\includestandalone[height=3.6cm]{figures/PowerDiagramSimplex_final} &
			\includestandalone[height=3.3cm]{figures/Voronoi1sym_curves} &
			\includestandalone[height=3.3cm]{figures/Voronoi1sym} \\
			(a) & (b) & (c)
		\end{tabular}}
		\caption{Farthest power diagram, logarithmic deformation, and asymmetric tropical Voronoi diagram; see Example~\ref{exmp:PowDiag}.}
		\label{fig:PowDiag}
	\end{figure}
	
	\begin{remark}
		Observe that the tropicalization $\val^*(\bm S)=-S$ to the negative is natural here, as we are mapping points with Puiseux coordinates to (apices of) tropical halfspaces.
	\end{remark}
	
	\begin{remark}\label{rem:sufficiently-generic}
		We want to emphasize that lattices of rank at least two with rational entries are never in general position.
		To see this, consider two linearly independent elements $a$ and $b$ of the lattice.
		If any entry of $a$ or $b$ is zero, then $\0$ and $a$ or $b$ are not in general position.
		Otherwise, we can find $\mu,\nu\in\ZZ\setminus\{0\}$ such that $\mu a_1=\nu b_1$, due to the rationality of the lattice.
		Yet $\mu a$ and $\nu b$ are distinct, as $a$ and $b$ are linearly independent.
		So $\mu a - \nu b\neq\0$ is a lattice vector whose first coefficient vanishes; thus $\0$ and $\mu a - \nu b$ are not in general position.
		Consequently, Theorem~\ref{th:PuiseuxLift} cannot be applied to rational lattices directly.
		However, scrutinizing the proof reveals that the general position assumption is relevant only for those points whose Voronoi regions intersect.
		This leads us to considering \enquote{sufficiently generic} $(r,R)$-systems in Section~\ref{sec:delaunay} below.
	\end{remark}
	
	\begin{example} \label{exmp:PowDiag}
		Consider the sites $S=\{(1,1,-2), (-1,-1,2), (3,-6,-3), (-3,6,-3)\}$ in $\cH$.
		These are lifted to
		\[
		\bm S = \bigl\{ \, (t^{-1},t^{-1},t^2)\,,\; (t,t,t^{-2})\,,\; (t^{-3},t^6,t^{-3})\,,\; (t^3,t^{-6},t^3) \, \bigr\}
		\]
		in $\KK_{>0}^n$.
		The farthest power diagram of $\bm S$ is displayed in Figure~\ref{fig:PowDiag}~(a) by showing the picture over the reals obtained from substituting $t$ by the real number $1.6$.
		Actually, we show the intersection of the positive orthant with the hyperplane $x_1+x_2+x_3=1$, which is a unit simplex.
		Figure~\ref{fig:PowDiag}~(b) visualizes the image of that farthest power diagram under the logarithmic deformation $x \mapsto \log_t x$, for $t=1.6$.
		Finally, Figure~\ref{fig:PowDiag}~(c) shows the asymmetric tropical Voronoi diagram of $S$.
		For $t \to \infty$ the logarithmic deformation converges to Voronoi diagram pointwise.
		These images should be compared with \cite[Fig.~1]{ABGJ:SIREV}, which visualizes the logarithmic deformation of a single Puiseux polyhedron.
	\end{example}
	
	\begin{remark}
		Instead of farthest power diagrams and lower convex hulls (for defining regular subdivisions), we could use ordinary power diagrams and upper convex hulls.
		This amounts to exchanging the arguments in the asymmetric tropical distance function; see also Remark~\ref{rem:switch}.
	\end{remark}
	
	\section{A different view}
	\label{sec:general}

	Edelsbrunner and Seidel~\cite{Edelsbrunner+Seidel:1986} studied Voronoi diagrams for general metrics.
	In general, their construction is different from the approach of Amini and Manjunath \cite{RRlattice}, which we adopt here.
	Yet, for a discrete set $S$ in general position, the two concepts agree, and this is what we will show now.
	
	Following \cite[\textsection 3]{Edelsbrunner+Seidel:1986} we define a function $D_S:\cH\to 2^S$ by letting
	\begin{equation}\label{eq:voronoi-cell}
		D_S(x) \ := \ \bigSetOf{ a\in S }{ d_\triangle(x,a) = \min_{b\in S}d_\triangle(x,b) } \enspace.
	\end{equation}
	That function defines an equivalence relation $\equiv_S$ on $\cH$ via: $x\equiv_S y$ if and only if $D_S(x)=D_S(y)$.
	The equivalence classes of $\equiv_S$ partition $\cH$, and they are called \emph{V-cells} with respect to $S$.
	For $T\subseteq S$ we set
	\[
	V_T \ := \ \bigSetOf{ x\in\cH }{ D_S(x)=T } \enspace ,
	\]
	and this is a V-cell or empty.
	A V-cell $V_T$ such that $T=\{a\}$ is a singleton is the \emph{V-region} of the site $a$.
	Clearly, if $S$ is finite, then there are only finitely many V-cells.
	
	\begin{remark}\label{rmk:cardTgenpos}
		If a V-cell $V_T$ is nonempty and $S$ is in general position, then $|T|\leq n$.
		Indeed, if $|T|>n$ and there exists a point $x\in V_T$, then the pigeonhole principle would imply the existence of an index $i\in[n]$ and of at least two distinct sites $s,t\in T$ such that $d_\triangle(x,s)=n(x_i-s_i)$ and $d_\triangle(x,t)=n(x_i-t_i)$.
		Since $x\in V_T$, we must have $n(x_i-s_i)=d_\triangle(x,s)=d_\triangle(x,t)=n(x_i-t_i)$ which entails $s_i=t_i$.
		This cannot happen, as we assumed $S$ to be in general position.
		Similarly, any Voronoi cell $\bigcap_{a\in T}\VR_S(a)$ is empty when $|T|>n$ and $S$ is in general position.
	\end{remark}
	
	\begin{lemma}\label{lem:region-generic}
		Let $S\subset\cH$ be a discrete set of sites.
		Then the topological closure of the V-region $V_{\{a\}}$ is contained in the Voronoi region $\VR_S(a)$.
		If $S$ is in general position, then the closure of~$V_{\{a\}}$ equals $\VR_S(a)$.
	\end{lemma}
	\begin{proof}
		Let $x\in V_{\{a\}}$, \ie $D_S(x)=\{a\}$.
		Then $d_\triangle(x,a) \leq d_\triangle(x,b)$ for all $b\in S$, whence~$x\in\VR_S(a)$.
		That is, $V_{\{a\}}\subseteq\VR_S(a)$.
		As $\VR_S(a)$ is closed it contains the closure of~$V_{\{a\}}$.
		
		For the converse we assume that $S$ is in general position, and we pick a point $x$ in the interior of the Voronoi region $\VR_S(a)$.
		Then it is a consequence of Lemma~\ref{lem:bisector-generic} that $d_\triangle(x,a)<d_\triangle(x,b)$ for all sites $b\neq a$.
		That is, $D_S(x)=\{a\}$ or, equivalently, $x\in V_{\{a\}}$.
		The conclusion now follows from Lemma~\ref{lem:puredim}.
	\end{proof}
	
	For the sake of conciseness, we call the topological closure of a V-cell a \emph{closed V-cell}.
	Now we can prove that our tropical Voronoi diagrams agree with the construction in \cite{Edelsbrunner+Seidel:1986}, provided that the sites are in general position.
	This is based on the crucial fact that tropical hyperplane arrangements in general position essentially behave like ordinary hyperplanes in general position; \cf \cite[\textsection\textsection 7.5, 8.3]{ETC}.
	Observe that tropical polyhedra are ordinary polyhedral complexes, which thus have a dimension.
	This dimension agrees with the notion of \enquote{tropical rank} \cite[\textsection 5.3]{Tropical+Book}.
	
	\begin{theorem}\label{thm:V-cells}
		Let $S\subset\cH$ be a discrete set of sites in general position.
		Then the Voronoi cells in $\VD(S)$ are precisely the closed V-cells with respect to $S$.
		Moreover, the V-cell $V_T$ (and its closure) is of dimension $n-|T|$.
	\end{theorem}
	\begin{proof}
		
		Let $V_T$ be a V-cell.
		From its definition, it is clear that the closure of $V_T$ is a subset of $W_T:=\bigcap_{a\in T}\VR_S(a)$.
		In particular, if $W_T$ is empty, then also $V_T$ is empty.
		
		Now consider a nonempty set $T\subseteq S$ such that $W_T$ is a Voronoi cell, \ie it is not empty.
		We need to show that $W_T$ is the closure of the V-cell $V_T$.
		The case when $T$ is a singleton is covered by Lemma~\ref{lem:region-generic}, so we will assume that $|T|\geq 2$ from now on.
		Note that $|T|\leq n$ because $S$ is in general position; see Remark~\ref{rmk:cardTgenpos}.
		
		Since $T$ contains at least two sites, we can pick any $a\in T$ and write $W_T$ as the intersection $\bigcap_{b\in T\setminus\{a\}}\bisector(a,b)$.
		Now the general position comes in twice.
		First, by Lemma~\ref{lem:bisector-generic} the bisectors are boundary planes of tropical halfspaces.
		Second, the tropical halfspace arrangement induced by those boundary planes is generic.
		Hence, via lifting to Puiseux series that tropical halfspace arrangement has the same intersection poset as an ordinary hyperplane arrangement over Puiseux series; see \cite[\textsection 8.3]{ETC}.
		That is, the set $W_T$ is a complete intersection, and thus $W_T$ is the closure of~$V_T$.
		This also proves that $W_T$ is an ordinary polyhedral complex of pure dimension $n-|T|$.
	\end{proof}
	
	The proof above gives a somewhat high-level view of the situation.
	The key idea is to employ lifts to Puiseux series, similar to what we did in Section~\ref{sec:power}.
	The example below shows that the assumption on general position is essential.
	
	\begin{example} \label{exmp:V-cell}
		Consider the sites $c=(-5,-5,10)$ and $d=(-5,10,-5)$ from Example~\ref{exmp:non-generic}, which are \emph{not} in general position.
		The Voronoi region $\VR_{\{c,d\}}(d)$ consists of the union of the striped area and the orange area in Figure~\ref{fig:V-cell}, including the boundaries.
		However, the V-region of $d$ consists only of the striped area, without the boundaries.
		Even when we take the closure of the V-region, we do not obtain the tropical Voronoi region.
		The perspective of Edelsbrunner and Seidel allows for full-dimensional regions that cannot be associated with a unique site.
		For example, the V-cell~$V_{\{c,d\}}$ contains the orange region and the three rays that emanate from the origin.
	\end{example}
	
	\begin{figure}[t]
		\centering
		\includestandalone{figures/v_cell}
		\caption{V-regions vs. Voronoi regions; see Example~\ref{exmp:V-cell}.}
		\label{fig:V-cell}
	\end{figure}
	
	Boissonnat et al.\ \cite[\textsection 8.2]{BSTY1998} developed an incremental algorithm for computing Voronoi diagrams in the sense of \cite{Edelsbrunner+Seidel:1986} for simplicial distance functions.
	By \cite[Theorem~5.1]{BSTY1998} there are at most $\Theta(m^{\lceil (n-1)/2\rceil})$ many V-cells, for $n$ fixed.
	In \cite[Theorem~8.8]{BSTY1998} the authors show that the tropical Voronoi diagram of $m$ sites in $\torus{n}$ in general position can be constructed incrementally in randomized expected time $O(m \log m + m^{\lceil (n-1)/2\rceil})$.
	This agrees with the complexity to compute Euclidean Voronoi diagrams \cite[Corollary~17.2.6]{BoissonnatYvinec:1998}.
	However, it is faster than the algorithm in \cite[Theorem~10]{TropBis} for computing tropical Voronoi diagrams with respect to the symmetric tropical distance; that expected time complexity bound is $O(m^{n-1}\log m)$.
	Note that the algorithms of \cite{BoissonnatYvinec:1998} and \cite{TropBis} produce different types of output.
	
	\section{Delone complexes and Laurent monomial modules}
	\label{sec:delaunay}

	For super-discrete sites in general position, by Theorem~\ref{th:PuiseuxLift}, the combinatorial type of the asymmetric tropical Voronoi diagrams is preserved in the lift to generalized dual Puiseux series $\KK=\hahnseries{\RR}{t}^*$.
	Recall that this combinatorial type is defined as the intersection poset of the Voronoi regions.
	Here, we show how such posets occur in commutative algebra.
	To this end, we consider the \emph{monomial lifting function}
	\begin{equation}
		\mu : \cH\to\bm\cH \,,\ s\mapsto t^{-s} \enspace,
	\end{equation}
	where $t^{-s}=(t^{-s_1},\dots,t^{-s_n})$.
	First we assume that $S$ is a finite set of sites and $\bm S=\mu(S)\subset\bm\cH$ is its \emph{monomial lift}.
	For monomial lifts substituting $t$ by any positive real number is well-defined.
	In this way, $\PD(\bm S)$ gives rise to a family of power diagrams $\PD(\bm S(t))$ over the reals which depend on a real parameter $t$; see Figure~\ref{fig:PowDiag}.
	The cells of a power diagram, over $\KK$ or $\RR$, are partially ordered by inclusion.
	We observe that farthest power diagrams over Puiseux series behave like farthest power diagrams over the reals, in the following precise sense.
	
	\begin{lemma}\label{lem:PDS-vs-PDSt}
		Let $S\subset\cH$ be a finite set of sites in general position with monomial lift $\bm S=\mu(S)$.
		Then the Puiseux farthest power diagram $\PD(\bm S)$ is isomorphic to the boundary complex of an ordinary polyhedron over the ordered field\/ $\KK$ of real Puiseux series.
		Moreover, for any $t$ large enough, $\PD(\bm S)$ and $\PD(\bm S(t))$ are isomorphic as posets.
	\end{lemma}
	\begin{proof}
		The first claim follows from \cite[\textsection 4]{PowDiag}, which treats power diagrams over the reals.
		The polyhedral geometry over arbitrary ordered fields is discussed in \cite[Appendix~A]{ETC}.
		The second claim is given by \cite[\textsection 8.5]{ETC}.
		It is explained in \cite[Theorem~12]{ABGJ:2018} how to find a number $t_0>1$ such that $\PD(\bm S)$ and $\PD(\bm S(t))$ are isomorphic as posets for all~$t>t_0$.
	\end{proof}
	Lemma~\ref{lem:PDS-vs-PDSt} holds for more general lifting functions.
	Yet, by restricting to the specific function~$\mu$ we avoid questions concerning convergence of Puiseux series.
	Moreover, properties of the function~$\mu$ enter the quantitative analysis in \cite[Theorem~12]{ABGJ:2018}.
	
	Now we pass to the case, where $S$ is both super-discrete and an $(r,R)$-system, with $0<r<R\leq\infty$, but not necessarily in general position.
	Recall that this includes the situation in which $S$ is an arbitrary finite set of sites.
	Then we can dualize the asymmetric tropical Voronoi diagrams as follows.
	
	\begin{figure}[t]
		\includestandalone[width=9.5cm]{figures/Voronoi1sym_detailed}
		\caption{Voronoi diagram and corresponding nonpure Delone complex.}
		\label{fig:non-pure}
	\end{figure}
	
	\begin{definition}\label{def:delaunay}
		The \emph{(asymmetric tropical) Delone complex} $\Del(S)$ is defined as the clique complex of the dual graph of the Voronoi diagram $\VD(S)$.
	\end{definition}
	The nodes of the dual graph of $\VD(S)$ are the Voronoi regions, and they are adjacent if their intersection has codimension at most one.
	A \emph{clique} in a graph is a subset of the nodes such that any two nodes in the set are connected by an edge.
	The cliques form an abstract simplicial complex, which is called the \emph{clique complex}.
	Such simplicial complexes are also called \enquote{flag simplicial complexes.}
	Delone complexes do not need to be pure; see Example~\ref{exmp:non-pure}.
	
	\begin{example} \label{exmp:non-pure}
		Consider the Voronoi diagram depicted in Figure~\ref{fig:non-pure}, generated by the four sites in the plane from Example~\ref{exmp:PowDiag}.
		The boundaries of the Voronoi regions are drawn in orange, while the Delone complex is purple.
		The Delone complex is not pure, since it has one triangle and one segment as its maximal cells.
		Observe that the four sites are symmetric with respect to the origin.
		However, that symmetry is not compatible with tropical convexity.
		This is why neither the Voronoi diagram nor the Delone complex are symmetric.
	\end{example}
	
	Again, we let $\bm S=\mu(S)$ be the monomial lift.
	Now we additionally assume that~$S$ is in general position, while we also keep our previous assumption that $S$ is a super-discrete $(r,R)$-system.
	By Theorem~\ref{th:polySuperDisc} each Voronoi region $\VR(s)$ is a $\max$-tropical polyhedron, and by Theorem~\ref{th:PuiseuxLift} the monomial lift of $\VR(s)$ is an ordinary polyhedron over $\KK$.
	We conclude that $\PD(\bm S)$ is a polyhedral complex over $\KK$, which may be infinite.
	Similarly, $\PD(\bm S(t))$ is a polyhedral complex over the reals.
	Thanks to $S$ being an $(r,R)$-system there is a uniform bound for $t$ relative to every cell.
	Note that the upper bound $R$ is not required in the argument, whence that uniform bound exists for $(r,\infty)$-systems, too.
	It follows that Lemma~\ref{lem:PDS-vs-PDSt} is valid for super-discrete $(r,R)$-systems in general position.
	
	\begin{lemma}\label{lem:delaunay}
		Let $S\subset\cH$ be a super-discrete $(r,R)$-system in general position, for $0<r<R\leq\infty$.
		Then the Delone complex $\Del(S)$ is dual to $\VD(S)$ as a partially ordered set.
	\end{lemma}
	\begin{proof}
		The results from Section~\ref{sec:general} apply, and we use the map $D_S:\cH\to S$ defined in~\eqref{eq:voronoi-cell}.
		In view of Theorem~\ref{thm:V-cells}, the set $T\subseteq S$ forms a cell of $\Del(S)$ if and only if the closure of $V_T$ is a Voronoi cell.
	\end{proof}
	
	We want to describe the Puiseux power diagram $\PD(\bm S)$.
	In our case, according to~\cite[\textsection 4.1]{PowDiag}, it is gotten from the graph of the function $\bm x \mapsto \max_{\bm s\in\bm S} (-\bm s^\top \bm x)$.
	The minus sign comes from considering farthest point power diagrams.
	After intersecting the epigraph with $\KK^n_{\geq 0}$, the dual is isomorphic to $\conv(\bm S)+\KK^n_{\geq 0}$.
	Since Lemma~\ref{lemma:polyPR} gives the polyhedrality of the Voronoi cells in $\PD(\bm S)$, a result of Klee \cite[Corollary~5.14]{Klee:1959} implies that $\conv(\bm S)+\KK^n_{\geq 0}$ is quasi-polyhedral.
	The faces of $\PD(\bm S)$ touching $\KK^n_{\geq 0}$ map to the unbounded faces of $\conv(\bm S)+\KK^n_{\geq 0}$.
	This leads to the following result.
	
	\begin{figure}[t]
		\begin{tabular}{cc}
			\includestandalone[width=6.1cm]{figures/OtherLattice2+Del} &
			\includestandalone[width=6.1cm]{figures/latticePert} 
		\end{tabular}
		\caption{Left: Delone complex of nine sites arising from Example~\ref{exmp:lattice}.  Right: Delone complex of the generic perturbation by~$\epsilon=1/10$.}
		\label{fig:Del}
	\end{figure}
	
	\begin{theorem}\label{th:delaunay}
		Let $S\subset\cH$ be super-discrete $(r,R)$-system in general position, for $0<r<R\leq\infty$.
		Then, for any $t$ sufficiently large, the Delone complex $\Del(S)$ is isomorphic to the bounded subcomplex of $\conv\smallSetOf{t^{-s}}{s\in S}+\RR^n_{\geq 0}$, which is an unbounded ordinary convex quasi-polyhedron in $\RR^n$.
	\end{theorem}
	
	We call a super-discrete $(r,R)$-system $S$ \emph{sufficiently generic} if any two sites whose Voronoi regions intersect are in general position.
	In \cite{RRlattice} the authors discuss generic perturbations of rational lattices.
	These form our key examples, such as the following.
	
	\begin{example}\label{exmp:perturb}
		We consider the lattice $L=L_2(2,1,1)$ from Example~\ref{exmp:lattice}, which is rational.
		Further, we pick a small rational $\epsilon>0$ to define the lattice $L^\epsilon$ with generators $b_0^\epsilon=(2+2\epsilon,-2-\epsilon,-\epsilon)$ and $b_1^\epsilon=(-1-\epsilon,2+2\epsilon,-1-\epsilon)$.
		The lattice points in $L^\epsilon$ are sufficiently generic but not in general position.
		The origin has eight adjacent Voronoi regions in $\VD(L)$.
		Its Voronoi region is depicted in Figure~\ref{fig:Del}, with and without perturbation.
		Locally, the situation is fully described by nine points in $L$ and their perturbations.
		The simplicial complexes $\Del(L)$ and $\Del(L^\epsilon)$ are three- and two-dimensional, respectively.
	\end{example}
	
	Finally, we turn to commutative algebra.
	We view the Laurent polynomial ring $\FF[x_1^\pm,\dots,x_n^\pm]$ over some field $\FF$ as an algebra over the polynomial ring $\FF[x_1,\dots,x_n]$.
	To be able to make the connection with asymmetric tropical Voronoi diagrams, we now additionally assume that the sites in $S$ have integral coordinates; \ie $S\subset\cH\cap\ZZ^n$.
	Then we obtain the \emph{Laurent monomial module}
	\begin{equation}\label{eq:monomial-module}
		M(S) \ = \ \bigl[ \, x_1^{-s_1}\dots x_n^{-s_n}:s\in S \, \bigr] \enspace,
	\end{equation}
	which is the submodule of $\FF[x_1^\pm,\dots,x_n^\pm]$ spanned by the monomials $x_1^{-s_1}\dots x_n^{-s_n}$.
	Monomial modules and their resolutions have been studied by Bayer and Sturmfels~\cite{BayerSturmfels:1998}; see also \cite[\textsection 9.2]{CombCommAlg}.
	Note that Laurent monomial modules are not necessarily finitely generated.
	In our setting, the bounded subcomplex of $\conv\smallSetOf{t^{-s}}{s\in S}+\RR^n_{\geq 0}$ is known as the \emph{hull complex} of $M(S)$; see \cite[\textsection 4.4]{CombCommAlg}.
	This is known to be isomorphic to the Scarf complex, when we assume (sufficient) genericity; see \cite[Theorem~9.24]{CombCommAlg}.
	In view of Remark~\ref{rem:sufficiently-generic}, Theorem~\ref{th:delaunay} applies.
	
	\begin{corollary}\label{cor:scarf}
		Let $S\subset\cH\cap\ZZ^n$ be a subset of a lattice which is sufficiently generic.
		Then the Delone complex $\Del(S)$ is isomorphic as a simplicial complex to the hull complex of the Laurent monomial module $M(S)$.
	\end{corollary}
	
	\begin{proof}
		Theorem~\ref{th:PuiseuxLift} holds for $S$ as the defining halfspaces of any Voronoi region are induced by sites in general position. 
		So the result is a direct consequence of Theorem~\ref{th:delaunay}.
	\end{proof}
	
	Connections between monomial ideals/modules and tropical geometry have been discussed in \cite{DevelinYu07,ManjunathSturmfels:2013,Loho+Smith:2019} and elsewhere.
	In \cite{MonCon} it was shown that this connection can be exploited in multicriteria optimization \cite{Ehrgott:2005}.
	Seeing the exponents of monomials as points in $\RR^n$ leads to geometric objects called \emph{staircases} in \cite[\textsection 3]{CombCommAlg} which are tropical cones in the view of \cite{MonCon} and \cite{Loho+Smith:2019}.
	In \cite[\textsection 4.3]{RRlattice} these cones are linked to tropical Voronoi diagrams.
	More exactly, the authors look at the epigraph of the function $\frac{1}{n}\min_{s\in S}d_\triangle(\cdot,s)$, which encodes the distance to the closest site.
	With the terminology from \cite{MonCon} and \cite{Loho+Smith:2019}, the epigraph is the tropical monomial cone generated by $-S$ and its boundary projects onto $\VD(S)$.
	For finitely many sites, the Voronoi diagram is isomorphic to the dual of the sub-lattice of the \enquote{vertex-facet lattice} (poset) of \cite[\textsection 3]{Loho+Smith:2019} induced by the finite generators, yet the Delone complex may be coarser than that sub-lattice.
	We close this paper with the analysis of a classical example, which also occurs in \cite[Corollary~28]{ManjunathSturmfels:2013}.
	
	\begin{figure}[t]\centering
		\includestandalone[width=8cm]{figures/DelA2} 
		\caption{Voronoi region $\VR_{A_2}(\0)$, whose six tropical vertices lie in the boundary of $-2\triangle$;  and Delone complex of $A_2$.}
		\label{fig:DelA2}
	\end{figure}
	
	\begin{example}
		The root lattice $A_{n-1}$ is generated by the vectors $e_i-e_j$, for $i,j\in[n]$; it lies in~$\cH$.
		The asymmetric tropical Voronoi diagrams of $A_{n-1}$ and its sub-lattices are studied in \cite[\textsection\textsection 4.2, 4.3]{RRlattice}.
		The tropical vertices of the Voronoi region $\VR_{A_{n-1}}(\0)$ are points with integral coordinates in the dilated simplex $-(n-1)\triangle$.
		The integer points in an intersection $\VR_{A_{n-1}}(x)\cap\VR_{A_{n-1}}(y)$ arise from the intersection of two translated copies of $-(n-1)\triangle$.
		If nonempty, that intersection is of the form $z-r\triangle$ for some $z\in\ZZ^n/\ZZ\1$, so $\dim(\VR_{A_{n-1}}(x)\cap\VR_{A_{n-1}}(y))=r$.
		We have $r=n-2$ if and only if $y=x+e_i-e_j$ for some distinct indices $i,j\in[n]$.
		This characterizes the dual graph of the Voronoi diagram $\VD(A_{n-1})$, from which we can derive the Delone complex.
		We remark that it coincides with the Euclidean Delone complex of $A_{n-1}$; see \cite[p. 85]{Conway+Sloane:91}.
		
		We conclude that $\Del(A_{n-1})$ is isomorphic to the standard triangulation of an apartment in the Bruhat--Tits building of the group $\SL_n(\FF)$ over a field $\FF$ with a discrete valuation; see \cite[pp. 753--754]{ManjunathSturmfels:2013} and \cite[Observation~10.82]{ETC}, for the connection to tropical convexity.
		In this way $\Del(A_{n-1})$ may also be seen as a geometric realization of the affine Coxeter group of type $\widetilde{A}_{n-1}$.
		An example for $\FF$ is given by the ordinary (dual) Laurent series with complex coefficients, which form a subfield of the field of generalized dual Puiseux $\hahnseries{\CC}{t}^*$.
		The computation above also shows that $A_{n-1}$, considered as a point configuration, is not sufficiently generic.
		Nonetheless, its Delone complex is pure of dimension $n-1$.
	\end{example}
	
	\bibliographystyle{mersenne-plain}
	\bibliography{ALCO_Comaneci_769}
	
\end{document}