Foundations of Computational Mathematics
https://doi.org/10.1007/s10208-021-09538-4
Tropical Bisectors and Voronoi Diagrams
Francisco Criado1·Michael Joswig1,2 ·Francisco Santos3
Received: 3 July 2019 / Revised: 30 January 2021 / Accepted: 27 May 2021
© The Author(s) 2021
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.
Keywords Polyhedral norms ·Polytropes ·Randomized algorithms ·Voronoi
diagrams
Mathematics Subject Classification 14T15 ·46B20 ·52B55
Communicated by Evelyne Hubert.
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.
BMichael Joswig
Francisco Criado
Francisco Santos
1TU Berlin, Chair of Discrete Mathematics/Geometry, Berlin, Germany
2Chair of Discrete Mathematics/Geometry; Max-Planck Institute for Mathematics in the Sciences,
Leipzig, Germany
3Departamento de Matemáticas, Estadística y Computación, Univ. de Cantabria, Santander, Spain
123
Foundations of Computational Mathematics
1 Introduction
One early route to the success of tropical geometry is based on the tropicalization
of classical algebraic varieties defined over some valued field. Key examples include
Mikhalkin’s correspondence principle, which relates tropical plane curves with clas-
sical complex algebraic curves [24], or the tropical Grassmannians of Speyer and
Sturmfels [25]. In all of this the focus lies on the combinatorial properties of tropical
varieties, which are ordinary polyhedral complexes.
More recently, however, tropical semi-algebraic sets and their intrinsic geometry
came into the picture; see [1,15]. For instance, their metric properties appear in [2]
as a tool to show that standard versions of the interior point method of linear pro-
gramming exhibit an exponential complexity in the unit cost model. The proof of
that result is based on translating metric data on a family of tropical linear programs
into curvature information about the central paths of their associated ordinary linear
programs. Similarly, tropical analogs of isoperimetric (or isodiametric) inequalities
have been studied in [8], where a tropical volume is defined that corresponds to an
“energy gap” in mathematical physics [19]. Another example is the statistical analysis
of phylogenetic trees by Lin, Monod and Yoshida [21].
We feel that all this calls for a more systematic investigation of metric properties of
tropical varieties. Starting from first principles, this naturally leads to tropical Voronoi
diagrams. The tropical distance between two points a,b∈Rd+1is
dist(a,b)=max
i∈[d+1](ai−bi)−min
j∈[d+1]aj−bj=max
i,j∈[d+1](ai−bi−aj+bj).
(1)
It does not depend on choosing min or max as the tropical addition. The map dist :
Rd+1×Rd+1→Ris non-negative, symmetric, and it satisfies the triangle inequality.
Moreover, it is homogeneous, so it induces a norm on the tropical d-torus Rd+1/R1∼
=
Rd, where 1=(1,...,1)denotes the all ones vector. The tropical Voronoi region of
a site s∈Swith respect to a set Scomprises those points in Rd+1/R1to which sis
the nearest among all sites in S, with respect to dist. The tropical Voronoi diagram
Vor(S)is the cell decomposition of Rd+1/R1into Voronoi regions. Tropical Voronoi
diagrams are a special case of Voronoi diagrams for polyhedral norms, a classical topic
in convexity and computational geometry; cf. [4, Sect. 7.2] or [23, Sect. 4].
The intersection of two or more Voronoi regions is part of a bisector, i.e., the locus
of points which are equidistant to a given set. For instance, in the Euclidean case the
bisector of two points is a degenerate quadric which agrees with an affine hyperplane
as a set. In the tropical setting, the bisector of two points can also be described as
part of a tropical hypersurface, but this is now of degree d+1; see Proposition 4.
Further, in the tropical case two points may already produce degenerate bisectors
(which may contain, e.g., full-dimensional pieces), whereas the first degenerate case
in the Euclidean metric arises for three points. So tropical Voronoi diagrams behave
quite differently from Euclidean Voronoi diagrams.
Yet there are also similarities. A key structural result is that the tropical Voronoi
regions are star convex and can be described as unions of finitely many ordinary poly-
123
Foundations of Computational Mathematics
hedra; see Proposition 1and Theorem 6. We prove a second main result, Theorem 3,
for the more general case of an arbitrary polyhedral norm in Rd: the bisector of any
three points in weak general position is homeomorphic to an open subset of Rd−2.Our
proof generalizes the arguments from [13], [14], where a similar result was proved for
smooth norms in d=2,3. However, the global topology of tropical bisectors of three
or more points can be radically different from the topology of the classical bisectors.
For instance, tropical bisectors are sometimes disconnected and, more strongly, d+1
points can have more than one circumcenter. This may happen even in general posi-
tion; see Examples 1and 3. We do not know if bisectors may have nontrivial higher
Betti numbers, but we suspect they can; see Theorem 4.
Another contribution in our paper is a randomized incremental algorithm for com-
putingthe tropical Voronoi diagram of npoints ingeneralpositioninRd+1/R1withan
expected running time of order O(ndlog n), for fixed dimension d; see Theorem 10.
Euclidean Voronoi diagrams of finite point sets can be explained fully in terms of
ordinary convex polyhedra and convex hull algorithms; see [4,7]. We do not know if
there is a tropical analog.
Amini and Manjunath [3] study the Voronoi diagram of a lattice with respect to the
following asymmetric version of the tropical distance:
dist(a,b)=max
i∈[d+1](ai−bi).
As they show in [3, Lemma 4.7], this is the polyhedral distance obtained taking as unit
ball the standard simplex. Their motivation comes from work of Baker and Norine [5]
on a Riemann–Roch theorem for graphs, which implies a Riemann–Roch theorem for
tropical curves.
Our paper is organized as follows. The short Sect. 2, in which we verify that the
tropical distance is induced by a polyhedral norm and discuss the combinatorics of
the tropical unit ball, sets the stage. In Sect. 3we collect our general structural results
on bisectors and Voronoi diagrams. The results in this section are proved for general
polyhedral norms, but all our examples address the tropical case. A subtle point is
the right concept of “general position”. In fact, we distinguish between weak general
position which prevents bisectors to contain full-dimensional parts (see Proposition 2),
and a stronger general position which is defined via stability of facets in the bisector
under perturbation of the sites. For instance, the bisector of any number kof points
in general position in Rdis either empty or a polyhedral complex of pure dimension
d+1−k; see Corollary 2. As a special case, the bisector of d+1 points in Rd
in general position is finite. Section 4returns to the tropical case. We specialize our
results on bisectors in general polyhedral norms, and we show that the combinatorial
types of tropical bisectors of two points are classified in terms of a certain polyhedral
fan related to the tropical unit ball and the braid arrangement; see Theorems 5and 6.
This is related to work of Develin [9] on the moduli of tropically collinear points.
Finally, in Sect. 5we discuss algorithms. This includes a tropical variant of Fortune’s
beach line algorithm [10] for planar Voronoi diagrams as well as the aforementioned
algorithm in arbitrary dimension.
123
Foundations of Computational Mathematics
2 The Tropical Unit Ball
The unit ball with respect to the tropical distance function defined in (1)is
Bd=x∈Rd+1/R1dist(x,0)=1=
i= jx∈Rd+1/R1xi−xj≤1
=1
2conv {±1}d+1\{±1}+R1.
(2)
In this way, Bdis a polytope in the tropical torus Rd+1/R1. We also write Bd(a,r)for
the tropical ball with center aand radius r. All tropical balls result from scaling and
translating Bd. In fact, the tropical norm agrees with polyhedral norm with respect to
the tropical unit ball, in the sense of Sect. 3. Such distances are called convex distance
functions in [4, Sect. 7.2]; see also [12–14].
Both the inequality and the vertex descriptions of Bdin Eq. (2) are non-redundant:
–Bdhas d(d+1)facets. Each facet corresponds to a choice of coordinates achieving
the maximum and the minimum.
–Bdhas 2d+1−2 vertices. Each vertex corresponds to a (nontrivial) partition of the
coordinates into maxima and minima. For example, B2is a hexagon and B3is a
rhombic dodecahedron.
The vertex description also shows that Bdequals the projection of the (d+1)-
dimensional regular cube [−1,1]d+1in Rd+1along the direction 1. That is, Bdis a
zonotope with d+1 generators in general position, and all its faces are parallelepipeds.
These generators correspond to the d+1 coordinate directions in Rd+1/R1.This
suggests a combinatorial way to specify the faces of Bd: Each face Fcan be written
as a Minkowski sum
F=
d+1
i=1
si,
where each siis one of {−ei},[−ei,ei]or {+ei}. We say that Fis of type (F−,F∗,F+)
if
F−={i∈[d+1]:si={−ei}},
F∗={i∈[d+1]:si=[−ei,ei]},
F+={i∈[d+1]:si={ei}}.
(3)
Conversely, a partition of [d+1]into three parts F−,F∗,F+corresponds to a face of
Bdif and only if neither F−nor F+is empty. Moreover, the dimension of Fequals
the cardinality of F∗. In particular, the vertices of Bdcorrespond to the 2d+1−2 ways
of partitioning [d+1]into two non-empty subsets. The facets of Bdcorrespond to the
d(d+1)ways of choosing an ordered pair from [d+1], without repetition (Fig. 1).
Remark 1 The zonotope Bdis dual to an arrangement of d+1 linear hyperplanes in
general position in Rd, oriented so that the intersection of all positive half-spaces is
123
Foundations of Computational Mathematics
Fig. 1 The tropical 3-ball B3,
with the conical hull of a facet
highlighted
empty. In particular, its face lattice is the same as the lattice of nonzero covectors of
the unique totally cyclic oriented matroid of rank dwith d+1 elements. Covectors of
an oriented matroid are usually written as (V−,V0,V+)but in our context we prefer
to use ∗instead of zero meaning that the corresponding coordinate is not fixed.
Remark 2 Another general description of Bdis that it equals the (ordinary) Voronoi
cell of the lattice of type Ad(i.e., the triangular lattice for d=2 and the face centered
cubic lattice (FCC) for d=3).
Similarly, Bdis the polytope polar to the difference body T−Tof a regular d-
simplex T. This description shows that Bdis the same as the polytope Udthat appears
in Makeev’s conjecture. See, e.g., [26, Conjecture 21.3.2].
3 Bisectors in Polyhedral Norms
Throughout this section we work in the general framework of Minkowski norms; see
[4, Sect. 7.2], [12], [23]. Consider a polytope K⊂Rdwith the origin in its interior.
Let dist(a,b)be the unique scaling factor α>0 such that b−a∈∂(αK). Then, dist
satisfies the triangle inequality, is invariant under translation, and homogeneous under
scaling. If K=−Kthen dist(a,b)=dist(b,a)and dist(0,·)is a norm in Rdin the
usual sense. We allow K=−K, whence dist(a,b)= dist(b,a)in general, but we
still call it a norm. Bisectors and Voronoi diagrams for these norms have been studied
in computational geometry [4, Sect. 7.2], [23, Sect. 4].
For any finite point set Swe define its bisector:
bis(S):= x∈Rddist(a,x)=dist(b,x)for a,b∈S.
Following the computational geometry tradition we will often call the elements of
Sthe sites. Although some of our results also hold for general convex bodies, for
simplicity we assume Kto be a polytope. We denote by F(K)the face fan of K.The
123
Foundations of Computational Mathematics
Fig. 2 Left: A point, p, in the tropical bisector of aand b. Right: The analogous picture, in classical
geometry
norm dist(0,·)is linear in each of these cones, so we write
bis(F1,...,Fk)({a1,...,ak})=bis({a1,...,ak})∩a1+F1∩···∩ak+Fk,
for the intersection of the bisector with a choice of cones Fi∈F(K). Each cell of
the form bis(F1,...,Fk)(a1,...,ak)is the intersection of the polyhedron (a1+F1)∩
···∩(ak+Fk)with an affine subspace, which implies it is itself a polyhedron. As a
consequence:
Proposition 1 Let K be a polytope with the origin in its interior, and let dist be the
corresponding Minkowski norm. Let S ={a1,...,ak}⊂Rdbe a finite point set. Then
the bisector bis({a1,...,ak})is a polyhedral complex whose cells are the polyhedra
bis(F1,...,Fk)(a1,...,ak)
for all choices of F1,...,Fk∈F(K).
Proof The family of polyhedra
bis(F1,...,Fk)(a1,...,ak), with F1,...,Fk∈F(K),
forms a polyhedral complex since
bis(F1,...,Fk)(S)∩bis(F
1,...,F
k)(S)=bis(F1∩F
1,...,Fk∩F
k)(S).
That polyhedral complex covers the entire bisector since for each point p∈bis(S)
and for each i, the point aimust lie in some face Fiof p−dist(ai,p)K.
Ourprimaryexampleisthecasewhere K=Bdisthetropicalball.InFig.2thepoint
p, which is generic within the bisector of aand b, lies in the facet bis(−∗+),(+−∗)(a,b).
123
Foundations of Computational Mathematics
For the purpose of drawing pictures, notice that any three vectors v1,v
2,v
3∈R2with
v1+v2+v3=0 define a map from R3/R1to R2via ei→ vi. While v1=(1,0),
v2=(0,1),v3=(−1,−1)is a common base for diagrams in tropical geometry, for
our pictures we settle for the more symmetric isometric view where our base is:
v1=−sin 2π
3,cos 2π
3,v
2=sin 2π
3,cos 2π
3,v
3=0,1.
Remark 3 If bis(a1,...,ak)=∅then bis(a
1,...,a
k)=∅for every choice of
a
1,...,a
ksufficiently close to a1,...,ak, by continuity of dist(·,·).
3.1 Weak General Position and General Position
Definition 1 (General position) A finite point set S⊂Rdis in general position with
respect to K, if for every subset {a1,...,ak}⊂Sthere are neighborhoods Uiof each
aisuch that for every choice of {a
1,...,a
k}with a
i∈Uiand for every choice of
maximal cones F1,...,Fk∈F(K)we have
bis(F1,...,Fk)(a1,...,ak)=∅ ⇐⇒ bis(F1,...,Fk)(a
1,...,a
k)=∅.
Moreover, the set Sis in weak general position if no pair of points a,b∈Slies in
a hyperplane parallel to a facet of K.
Remark 4 As the name suggests, “weak general position” is implied by “general posi-
tion” (see Corollary 1). A yet stronger notion would arise requiring stability not only
of facets but also of lower-dimensional cells in bisectors; that is, allowing lower-
dimensional cones from F(K)for the Fiin the definition of general position. But
this intermediate notion of “general position” is the most appropriate for our pur-
poses and the algorithms in Sect. 5. As a first indication, Theorem 1provides a local
characterization.
By Proposition 1bisectors are polyhedral complexes, and thus each cell has a
dimension.
Proposition 2 Two points a,b are in weak general position if and only if bis(a,b)
does not contain full-dimensional cells.
Proof Since bis(F,F)(a,b)⊂(a+F)∩(b+F), for it to be d-dimensional we need
Fand Fto be cones of facets. We also need F=F, so that dist(a,·)and dist(b,·)
have the same gradient on (a+F)∩(b+F), and we need b−ato be parallel to the
facet, so that dist(a,·)=dist(b,·)on (a+F)∩(b+F).
Conversely, if b−ais parallel to a facet of Kwith cone Fthen
bis(F,F)(a,b)=(a+F)∩(b+F),
and this is d-dimensional.
123
Foundations of Computational Mathematics
Corollary 1 General position implies weak general position.
Proof Suppose a−bis parallel to a facet of K, so that bis(F,F)(a,b)is full-
dimensional, where Fis the cone of that facet. Taking bclose to bbut away from the
hyperplane parallel to the facet makes bis(F,F)(a,b)empty. Now the claim follows
from Proposition 2.
Theorem 1 Let S ={a1,...,ak}⊆Rdand for each aichoose a maximal cone
Fk∈F(K). Let Q := (a1+F1)∩···∩(ak+Fk),letλFi(x)be the linear function that
restricts to dist(0,x)on Fi, and let H be the affine subspace defined by λF1(x−a1)=
···=λFk(x−ak).
Then, the following conditions are equivalent:
1. There are neighborhoods Uiof each aisuch that for any choice of a
i∈Uithe
polyhedron bis(F1,...,Fk)(a
1,...,a
k)is not empty.
2.(a) Q is full-dimensional and H intersects its interior; and
(b) the k −1functions λFi−λF1for i =2,...,k are linearly independent.
Since
bis(F1,...,Fk)(a1,...,ak)=Q∩H(4)
condition (a) is equivalent to “bis(F1,...,Fk)(a1,...,ak)meets the interior of Q”.
Proof For the implication from “1” to “2”, let us first show that “1” forces Qto be
full-dimensional. Aiming for a contradiction, we assume that Qis contained in the
boundary of one of the cones ai+Fi. That is, the polyhedron Qi:= j=i(aj+Fj)
does not meet the interior of ai+Fi,forsomei. Then any a
iin the interior of ai+Fi
yields (a
i+Fi)∩Qi=∅. Hence bis(F1,...,Fk)(a
1,...,a
k)=∅, where a
j=ajfor
j= i. This contradicts “1” and shows that Qis full-dimensional.
To see that bis(F1,...,Fk)(a1,...,ak)must intersect the interior of Q, suppose we are
given neighborhoods Uias in “1”; recall (4). For each i, choose viin the interior of
Fiand such that λi(vi)=1. Let a
i:= ai+vi, where >0 is taken small enough
so that a
i∈Ui. Observe that our choice of vimakes the affine subspace defined by
λF1(x−a
1)=···=λFk(x−a
k)agree with H.LetQ:= (a
1+F1)∩···∩(a
k+Fk),
which lies in the interior of Q.Wehave
bis(F1,...,Fd+1)(a
1,...,a
d+1)=Q∩H.
By “1” this is not empty, and thus Hintersects the interior of Q.
For condition (b) observe that Hcan equivalently be defined by the k−1 affine
equalities
(λFi−λF1)(x)=λFi(ai)−λF1(a1)for i=2,...,k.(5)
If the left-hand sides are linearly dependent, then one of the k−1 equations, say
the ith one, is redundant. But then choosing a point a
i∈Uiwith λFi(a
i)= λFi(ai)
123
Foundations of Computational Mathematics
(and letting a
j=ajfor the rest) renders the system of equations infeasible. Hence
bis(F1,...,Fd+1)(a
1,...,a
d+1)=∅, contradicting “1”.
We now show that “2” implies “1”. Consider arbitrary points a
i, and let Q
i=
i(a
i+Fi). Further let Hbe the affine subspace defined by
λF1(x−a
1)= ··· = λFk(x−a
k),
so that
bis(F1,...,Fk)(a
1,...,a
k)=Q∩H.
We want to show that if each a
iis sufficiently close to the corresponding aifor all i
then Q∩His not empty.
Condition (b) says that His (d+1−k)-dimensional (and parallel to H) for every
choice of a
is and that it varies continuously with the choice. Condition (a) says that
Qstays full-dimensional if the a
is are sufficiently close to the original ais, and that
it also varies continuously with the choice, in the following strong sense: consider a
description of each ai+Fiby a finite system of linear inequalities. Then a
i+Fiis
defined by a system with the same linear functions and with right-hand sides varying
continuously with the a
is.
Thus, if each a
iis close to ai, then Qand Hare a full-dimensional polyhedron
and a (d+1−k)-dimensional affine subspace close to Qand Hrespectively. Since, by
(a), Hintersects the interior of Q, continuity implies that Hstill intersects the interior
of Qwhen a
iis close enough to aifor each i. In particular, bis(F1,...,Fk)(a
1,...,a
k)
is not empty.
Corollary 2 The bisector of k points in general position is either empty or pure of
dimension d +1−k. In particular, the bisector of d +1points in general position is
finite, and this is empty for more than d +1points.
Proof Every maximal non-empty cell bis(F1,...,Fk)(a1,...,ak)is the intersection of
the polyhedron Qwith the affine subspace Hof Theorem 1. That result implies that
Hhas dimension d+1−kand meets the interior of the full-dimensional polyhedron
Q. Thus, the cell has dimension d+1−k.
Corollary 3 If every subset of at most d +2points in S is in general position then so
is S.
Corollary 4 For any n ≥1, the sequences of n points in Rdin general position form
an open dense subset of (Rd)n.
Proof Let S⊂Rdbe a set of cardinality n. Then Sis in general position if and
only if, for each subset {a1,...,ak}⊂Sand maximal cones F1,...,Fk∈F(K),
the polyhedron bis(F1,...,Fk)(a1,...,ak)either is empty or satisfies condition (1) of
Theorem 1. Since there are finitely many choices of {a1,...,ak}and {F1,...,Fk},it
suffices to prove the statement for one such choice.
Foropenness: Emptyness is an open condition because of the continuity of dist(·,·).
On the other hand, Theorem 1says that condition (1) is equivalent to (2), which is open
123
Foundations of Computational Mathematics
by the arguments in the proof (namely, the fact that both Qand Hdepend continuously
on the sites).
For density, we are going to show that if Q∩His not empty but fails to satisfy
condition (a) or (b) then the set {a1,...,ak}lies in one of finitely many linear hyper-
planes in (Rd)k. To emphasize that Qand Hdepend on the choice of sites we denote
them Q(a1,...,ak)and H(a1,...,ak).
If (b) fails for {a1,...,ak}then the linear system (5) defining H(a1,...,ak)is
feasible but overdetermined, which implies a linear relation, depending solely on
F1,...,Fk, among the right-hand sides λFi(ai)−λF1(a1). The relation is not tauto-
logical on the ais since, as shown in the Proof of Theorem 1, it is easy to construct a
point set {a
1,...,a
k}with H(a
1,...,a
k)=∅.
For (a), consider the inequality descriptions of the cones Fiand translate them to
obtain an inequality description of Q(a1,...,ak)as the feasibility region of a system
S(a1,...,ak)of affine inequalities with fixed gradients and with right-hand sides
parameterized linearly by the ais. If (a) fails for {a1,...,ak}then one of two things
happen:
–Q(a1,...,ak)is non-empty but not full-dimensional. Consider a minimal subsys-
temofS(a1,...,ak)thatalreadydefinesanon-full-dimensionalfeasibilityregion.
Minimality implies that this feasibility region is an affine subspace of Rdand that
turning the inequalities to equalities produces an over-determined subsystem. This
implies, as in the previous case, a linear relation among the ais.
–Q(a1,...,ak)is full-dimensional but Q(a1,...,ak)∩H(a1,...,ak)is contained
in its boundary. This implies that Q(a1,...,ak)∩H(a1,...,ak)is contained in
a facet of Q(a1,...,ak).LetH0(ai)be the hyperplane containing that facet. Note
that the hyperplane H0depends only on one aisince it comes from the description
of one of the cones ai+Fi. Then, adding to the the linear system (5) the equation
defining H0(ai)produces again an over-determined system, hence there is a linear
relation among the ais.
The relations for condition (a) are not tautological on the ais since we can easily make
Q(a
1,...,a
k)full-dimensional and H(a
1,...,a
k)intersect its interior as follows:
choose each a
iin the interior of −Fiand such that λFi(ai)=−1, so that both H
and the interior of Qcontain the origin. The relations are finitely many since we have
at most one for each subsystem (respectively equation) of the system S(a1,...,ak),
which depends only on the choice of Fis.
For the case of the tropical norm, condition (b) admits a nice combinatorial char-
acterization. Observe that a choice of facets F1,...,Fk∈F(Bd)can be encoded as a
directed graph on the vertex set [d+1]and with an arc aigoing from the coordinate
that is minimized at Fito the coordinate that is maximized at Fi,fori=1,...,k.We
denote this graph G(F1,...,Fk).
Proposition 3 For the case of the tropical norm, condition 2.(b) of Theorem 1holds if
and only if the graph G(F1,...,Fk)either has no (undirected) cycle or it has a unique
cycle and it is unbalanced; that is, the number of arcs in one direction is different from
the other direction.
123
Foundations of Computational Mathematics
Proof A cycle in G(F1,...,Fk)is equivalent to a linear dependence among the corre-
sponding linear functions λFis, by simply adding them with signs corresponding to the
direction of the arcs along the cycle. If the cycle is balanced then λF1can be subtracted
from each λFiso that the corresponding functions (λFi−λF1)are also dependent. The
same thing can be done if G(F1,...,Fk)has two different (unbalanced) cycles, since
a linear combination of the two corresponding dependences can be made balanced.
Conversely, any linear dependence among the functions (λFi−λF1)corresponds to
a balanced dependence among the corresponding λFi. The latter either corresponds to
a balanced circuit in the graph or decomposes into two (or more) linear dependences
with distinct supports.
As a consequence of Corollary 2the bisector of a set Sof d+1 points in general
position is a finite set of points, which we call circumcenters of S. In dimension two,
three points in (weak) general position have a most one circumcenter, as we show
in Corollary 6below. In higher dimension the same is known to be false for other
polytopal norms [13], and here is an example for the tropical norm:
Example 1 (Non-uniqueness of circumcenters) Let us consider the four points a1=
(0,2,3,3),a2=(0,4,2,2),a3=(2,4,1,1)and a4=(4,0,2,2). Their bisector
contains the points x=(0,0,1,−1)and y=(0,0,−1,1). Indeed, both xand yare
at distance 4 from all the ai’s since we have
a1−x=(0,2,2,4), a1−y=(0,2,4,2),
a2−x=(0,4,1,3), a2−y=(0,4,3,1),
a3−x=(2,4,0,2), a3−y=(2,4,2,0),
a4−x=(4,0,1,3), a4−y=(4,0,3,1).
The points a1,...,a4are not in weak general position, as they lie in the plane
x3−x4=0. However, they satisfy conditions (a) and (b) of Theorem 1for the poly-
topes Qxand Qycontaining the circumcenters xand y: For condition (b) observe
that the digraphs corresponding to xand yare, respectively, {14,12,32,21}and
{13,12,42,21}. They both have a single cycle, {12,21}, which is unbalanced. Con-
dition (a) follows from the fact that x(resp. y) is in the interior of all the cones whose
intersection defines Qx(resp. Qy). This is equivalent to the fact that all the vectors
ai−xand ai−yhave a unique maximum and a unique minimum entries.
Since condition (b) does not depend on the sites and condition (a) is, by Theorem 1,
open, any perturbation of the sites will still produce at least two circumcenters. In
particular, by Corollary 4, there are sites in general position for which this happens.
3.2 Halfspheres, Sectors, and the Bisector of Two Points
The topology of a bisector is closely related to the following partition of ∂K.Let
S⊆Rdbe a finite set of sites, and pick a,b∈Sdistinct. The open halfsphere in the
direction of b −a, denoted as H(b−a), is the set of points in ∂Kwhose exterior
normal cone is contained in (b−a)∨:= {λ|λ(b−a)>0}. Informally, H(b−a)are
123
Foundations of Computational Mathematics
the faces of Kthat “can be seen” from the direction (b−a). For a fixed site a∈S,
the sector of a is the set
HS(a)=
b∈S\{a}
H(b−a).
We denote HS:= {HS(a)|a∈S}. Observe that H(b−a)and, hence, HS(a),are
open in ∂K.
Lemma 1 Let F1,...,Fmbe the facets of K and let λFi(x)≤1be the valid linear
inequality defining Fi. Then, for each a ∈S,
HS(a)=relint FiλFi(a)<λ
Fi(b)for all b ∈S\a.
In particular, HS(a)∩HS(b)=∅for every a,b∈S and, if S is in weak general
position,
a∈S
HS(a)=∂K.
where HS(a)denotes the topological closure of HS(a).
Proof It is clear from the definition that HS(a)contains the relative interior of every
Fiwith λFi(a)<λ
Fi(b)for b∈S\a. By convexity of the cones {λ|λ(b−a)>0}
for each a,b,H(b−a)(hence HS(a)) also contains the relative interior of every
lower dimensional face contained only in such facets. This proves the first formula.
The second part follows from the first and the fact that in weak general position the
minimum of each λFiis attained at a single point of S.
Remark 5 Assuming weak general position, Lemma 1allows us to think of HSas a
labeling of the facets of Kby the elements of Sor, equivalently, as a map F(K)→S.
If Kis centrally symmetric, then each pair of opposite facets Fand −Fbelong one to
H(b−a)and the other to H(a−b).IfKis not, we can still guarantee that H(a−b)
is never empty, and always disjoint from H(b−a). As a consequence, H(b−a)(and
hence HS(a)) cannot contain all the (relative interiors of) facets of K.
For the case K=Bdof the tropical ball this partition of the facets translates into
something more meaningful. Recall (see Proposition 3and the paragraph before it)
that facets of Bdcan be represented as the arcs in the complete digraph on d+1 nodes.
In particular, HScolors the arcs by the points of S. Then:
1. Each coloring is a partial ordering of vertices, i.e. there is no monochromatic cycle.
2. For the case of two points in general position, the two colors are opposite acyclic
tournaments. In particular, there is a bijection between the possible halfspheres
H(b−a)and the total orderings of d+1 elements.
Theorem 2 ([13]ford =3) Let a,b∈Rdbe in weak general position. Then the
central projection from a induces a homeomorphism between bis(a,b)and a +H(b−
a). Hence, bis(a,b)is homeomorphic to Rd−1.
123
Foundations of Computational Mathematics
Proof Let us first show that bis(a,b)is contained in a+cone(H(b−a)). To seek a
contradiction, let c∈bis(a,b)such that c−a/∈cone(H(b−a)). This implies that
the smallest ball centered at athat contains ctouches it at a facet Fwith functional
λFsuch that λF(b−a)≤0. Now, cis equidistant to aand b, and aand bcannot be
in the same facet of the ball centered at c(because they are in weak general position).
Therefore,dist(c,a+(1−)b)<dist(c,a),byconvexityoftheball.Thiscontradicts
the fact that λFi(b−a)≤0.
Hence, we have a well-defined map φ:bis(a,b)→a+H(b−a)given by central
projection. The map φis continuous since it is the restriction of central projection. It
is also proper (that is, the inverse image of a compact set is compact) by a following
argument: Let Cbe a compact subset of H(b−a). By continuity, φ−1(C)is closed in
bis(a,b), hence in Rdsince bis(a,b)itself is closed (it is the zero set of the continuous
function d(x,a)−d(x,b)). Thus, we only need to prove that φ−1(C)is bounded. This
follows from the fact that
φ−1(C)⊂(a+cone(K)) ∩(b+cone(H(a−b))) ,
and that cone(C)and cone(H(a−b)) are two closed linear cones meeting only at the
origin, since H(a−b)and H(b−a)are open and disjoint in ∂K.
Once we know φis proper and continuous, we only need to check that this map is
bijective in order for it to be a homeomorphism. To show this, we construct its inverse.
For each v∈H(b−a)we consider the ray rv={a+αv :α≥0}. Along rv,the
distance to ais linear in α, the distance to bis convex in αand both functions are
continuous. Observe also that
dist(a+0v, a)=0,dist(a+0v, b)>0,
and lim
α→∞ dist(a+αv, b)< lim
α→∞ dist(a+αv, a).
The last inequality comes from the fact that as the we move farther away from aalong
rv, eventually (a+αv) −bwill be in the same cone of F(K)as (a+αv) −a=αv
(by weak general position), and b−a,v>0 since v∈H(b−a).
Hence, the function α→ dist(a+αv,b)−dist(a+αv, a)is negative at zero,
positive at infinity, continuous, and convex. Therefore, it has exactly one root, which
means rvintersects the bisector exactly once. We define ψ(a+v) as this unique
intersection point.
The maps φand ψare clearly inverses of one another.
Looking at the proof, the reader can check that central projection gives a proper and
continuous map from bis(a,b)to a+H(b−a)even without assuming weak general
position. We only need weak general position to construct the inverse.
Corollary 5 If S is in weak general position and there is an empty sector HS(a)∈HS
then the bisector of S is empty.
Proof Assume that there is a point c∈bis(S). For a site a∈Slet us show that
HS(a)=∅. By definition, c∈bis(a,b)for b∈S\{a}. By Proposition 2, each
123
Foundations of Computational Mathematics
bis(a,b)can be mapped to H(b−a)by central projection. Since cis in all of these
bisectors, the central projection of cinto the ball a+Klies in H(b−a)for all b, and
hence in HS(a).
The converse of Proposition 5is true for three points in arbitrary dimension (The-
orem 3) but not for more, even in general position, as the following example shows:
Example 2 (Empty bisector, with non-empty sectors) Consider a=(1,−1,0,0),
b=(−1,1,0,0),c=(0,0,2,−2)and d=(0,0,−2,2). Then we have
bis(a,b)=xx3+1≤x1,x2,≤x4−1
∪xx4+1≤x1,x2,≤x3−1∪xx1=x2.
By symmetry, we also have
bis(c,d)=xx1+2≤x3,x4,≤x2−2
∪xx2+2≤x3,x4,≤x1−2∪xx3=x4.
Since bis(a,b,c,d)lies in the intersection of the two, we have
bis(a,b,c,d)⊆xx1=x2,x3=x4.
So for x∈bis(a,b,c,d), we may assume x3=0, which entails:
dist(a,x)=max{x1+1,0}−min{x1−1,0}=max{|x1|+1,2}≤|x1|+2,
with equality only when x1=0 and
dist(c,x)=max{x1,2}−min{x1,−2}=max{|x1|+2,4}≥|x1|+2,
with equality only if |x1|≥2. This shows that bis(a,b,c,d)=∅.
However, HShas no empty sector since the sectors of a,b,c,dcontain the facets
with outer normals (1,−1,0,0),(−1,1,0,0),(0,0,1,−1)and (0,0,−1,1), respec-
tively. Both this property and the emptiness of bis(a,b,c,d)are preserved under
perturbation, so this behavior happens also in general position.
3.3 Bisectors of Three Points
The goal of this section is to prove our first main result.
Theorem 3 Let S ={a1,a2,a3}be a set of three distinct points in Rdwhich lie in
weak general position with respect to a polytope K . If HS(ai)=∅for i =1,2,3then
bis(a1,a2,a3)is homeomorphic to a non-empty open subset of Rd−2.
Corollary 6 For any three points in weak general position bis(a1,a2,a3)is either
empty or pure of dimension d −2.Ifd =2then bis(a1,a2,a3)is either empty or a
single point.
123
Foundations of Computational Mathematics
We begin with the case d=2 of Theorem 3; this occurs in [13]:
Lemma 2 Let S ={a1,a2,a3}⊂R2be in weak general position with respect to a
polytope K . If HS(ai)=∅for the three of them, then the bisector bis(S)is a single
point.
Proof We first show that bis(S)cannot contain two distinct points. To seek a contra-
diction, suppose that there are two points x= yin the bisector. This means that there
exist α, β > 0 such that Bx:= x−αKand By:= y−βKsatisfy S⊂∂Bx∩∂By.
For brevity we call Bxand Bynegative balls centered at xand y, respectively. The
two balls are related to one another by a homothety ρ:Bx→By.Leta
i:= ρ(ai)
and S={a
1,a
2,a
3}=ρ(S). Then, S∪S⊂∂By, but this is impossible: the vertex
sets of two homothetic triangles can only lie in the boundary of a polytope in the plane
if three of the points are collinear. Three collinear points of ∂Bynecessarily lie on a
single edge of By, and (at least) two of them would come from the same triangle Sor
S, violating the weak general position of S.
It remains to exclude the case where bis(S)=∅. Suppose that this would hold.
That is, the two-point bisectors are pairwise disjoint. Now the two-point bisectors are
homeomorphic to lines by Theorem 2. So the fact that they do not meet implies that
each of them appears either in full or not at all in the Voronoi diagram of S.Butthe
three of them cannot appear, since then the diagram would have four regions, not
three. Thus, one of them, say bis(a1,a3), does not appear at all in VorS. Consequently,
bis(a1,a3)is contained in the Voronoi region of the third point a2. We will show that
HS(a2)=∅, and this yields the desired contradiction.
To simplify the exposition, we call the line a1a3“horizontal”. Let uand vbe the
points where the ball Khas a horizontal tangent, i.e., parallel to a1a3. Without loss
of generality, uis at the top of K, and vis at the bottom; see Fig. 3. The points uand
vare unique and thus vertices of K, by weak general position. Consider the negative
tangent cones u+cone(u−K)and v+cone(v −K)of K.CallKuand Kvtheir
respective translations that have a1and a3on the boundary, and let uand vbe the
apices of these translated cones. Such translations exist and are unique since the two
boundary rays of cone(u−K)point upward, and the boundary rays of cone(v −K)
point downward.
By construction the boundaries of Kuand Kvintersect precisely in a1and a3.Now,
every negative ball of the form Bu,r:= u−r(K−u)has Kuas its tangent cone at
u, and balls like Bv,r:= v−r(K−v) are similar. Taking rsufficiently large, we
can force
Ku∩Kv=Bu,r∩Bv,r.
Since Bu,rand Bv,rare negative balls with a1and a3in their boundaries, their centers
lie on the bisector bis(a1,a3). Our initial assumption that the bisector is contained in
the Voronoi region of a2implies that a2is in the interior of both balls, i.e., in the
interior of both Kuand Kv. This implies that HS(a2)is empty: every facet-defining
functional of Ktakes its minimum on Ku∩Kvat either a1or a3.
We conclude that, if HS(ai)=∅for i=1,2,3 then bis(S)=∅, and this finishes
the proof.
123
Foundations of Computational Mathematics
u
v
K
a1
a2
a3
v
u
Fig. 3 Illustrating the Proof of Lemma 2. Left: polytope Kwith top and bottom vertices, uand v, horizontal
tangents and facet normals. Right: intersection Ku∩Kvwith a1and a3on the boundary. If a2∈Ku∩Kv
then all linear functions defined by exterior facet normals of Kor, equivalently, interior facet normals of
Kuand Kv, attain smaller values at a1or a3than at a2
For the rest of the Proof of Theorem 3let S={a1,a2,a3}⊂Rdbe three points in
general position with respect to a convex polytope K. The idea is to reduce the general
problem to two dimensions via the following construction. Let pr :Rd→Rd−2be
the affine projection that quotients out the 2-plane containing S. Next we exhibit
relevant properties of that map.
Lemma 3 With the above notation, let x ∈int(pr(K)) ⊂Rd−2. Further let x:=
pr−1(x),whichisa2-plane parallel to , and Kx:= K∩x. Then Kxis a convex
polygon.
Proof Thisisageneralpropertyofpolytopeprojections:if Qistheimageofapolytope
Punder an affine map then the fiber of every point x∈int(Q)is a polytope of
dimension dim(P)−dim(Q).
Lemma 4 With the above notation, again let x ∈int(pr(K)). Further, let H(x)
S(ai)
denote the sector of ai∈with respect to the polygon Kx. Then
H(x)
S(ai)=HS(ai)∩Kx.
Proof Note that no facet in Kxis parallel to any ai−ajbecause if it were, the facet
of Kcontaining it would be parallel, too.
Let Fbeafacetof Kx,andlet Fbethecorrespondingfacetin K.Then,n(F)∈x,
the normal vector to F, is the projection into of n(F), and,
123
Foundations of Computational Mathematics
F∈H(x)
S(ai)⇐⇒ n(F), ai>n(F), ajfor j=1,2,3
⇐⇒ n(F), ai>n(F), ajfor j=1,2,3
⇐⇒ F∈HS(ai).
Lemma 5 Let S ={a1,a2,a3}as before. If HS(ai)=∅for all i, then the intersection
ai∈Spr(HS(ai)) ⊂Rd−2is open and not empty.
Proof First, observe that an x∈∂Kwith pr(x)∈∂(pr(K)) cannot be in any of the
HS(ai): indeed, x∈∂Kimplies that there is a normal vector of Kat xorthogonal to
, hence orthogonal to ai−ajfor every ai,aj. As a consequence,
ai∈S
pr(HS(ai)) ⊂int pr(K),
which implies it is open.
For any point x∈int(pr(K)), the preimage pr−1(x)is a polygon, a slice of K.This
slice has to intersect at least two of the classes of H, because His a partition (so at the
slice intersects at least one class), but no class can contain a set of facets whose vectors
are positively dependent (because each class is an intersection of half-spheres). Then,
any point x∈int(K)lies in at least two sets pr(HS(ai)).
Thus, the three open sets pr(HS(ai)) cover each point of int(pr(K)) at least twice.
At least two of these sets must intersect, say pr(HS(a1)) and pr(HS(a2)). Suppose
that (pr(HS(a1)) ∩pr(HS(a2))) ∩pr(HS(a3)) =∅. Then, int(pr(K)) wouldbedis-
connected, because it is covered by two disjoint open sets. Since this is not possible,
there must be a point in the common intersection of the three HS(ai).
Our next lemma finishes the Proof of Theorem 3, and it actually gives more informa-
tion.
Lemma 6 The set bis(a1,a2,a3)is homeomorphic to i=1,2,3pr(HS(ai)).
Proof Consider the map
φ:bis(a1,a2,a3)−→
i=1,2,3
pr(HS(ai))
defined as follows: Let p∈bis(S), and let vi∈HS(ai)be the central projection from
pto ai+∂K, for each i=1,2,3. Note that each vilies in the corresponding HS(ai),
by Theorem 2. Further, the three points v1,v2and v3lie in a plane parallel to .In
particular, pr(v1)=pr(v2)=pr(v3)lies in i=1,2,3pr(HS(ai)) and we define
φ(p):= pr(vi).
To show that φis a homeomorphism, let us construct its inverse ψ.Letγ:
pr(int(K)) →int(K)be a continuous section of pr in K. For example, but not
123
Foundations of Computational Mathematics
p
r
a1
a2a3
Fig. 4 Construction of ψin the Proof of Theorem 3
necessarily, for each 2-plane parallel to and intersecting Klet γ(pr()) be the
centroid of ∩K.
Now, let x∈i=1,2,3pr(HS(ai)).Letx=pr−1(x)and let wi=γ(x)+ai,
for each i=1,2,3. In the 2-plane xwe have a set Sx={w1,w
2,w
3}and a unit
ball K∩x. Lemma 3gives that HSx(wi)=HS(ai)∩x. By choice of xwe have
iHSx(wi)=∅and Lemma 2guarantees that the bisector of Sxis a unique point
r∈x; see Fig. 4.
Let vibe the central projection of rto wi+∂Kx. Observe that |wir|/|wivi|is inde-
pendent of isince it equals distKx(wi,r), where distKxdenotes the distance induced
by Kxin R2, and ris in bisKX(w1,w
2,w
3). Since wi−ai=γ(x)is also independent
of i, the three rays aivimeet at the point
p=r+distKx(wi,r)γ (x),
and distK(ai,p)=distKX(wi,r). Thus, p∈bis(a1,a2,a3)and we define pto be
ψ(x).
This gives us a well-defined map
ψ:
i=1,2,3
pr(HS(ai)) −→ bis(a1,a2,a3),
and by construction ψis the inverse of φboth ways. The map γis continuous, as the
bisector of three points in the plane depends continuously on a continuous deformation
of the unit ball. So ψis continuous. Thus, φand ψare homeomorphisms between
bis(a1,a2,a3)and i=1,2,3pr(HS(ai)). Since the latter is not empty and open by
Lemma 5, the former is homeomorphic to a non-empty open subset of Rd−2.
Our Proof of Theorem 3closely follows the proof of the 3-dimensional case in
[14]. There, it is additionally shown that the number of connected components of
bis(a1,a2,a3)equals the total number of connected components of the three sectors
HS(a1)minus two. We can extend this formula to higher dimension and to higher
Betti numbers (over any field):
123
Foundations of Computational Mathematics
Theorem 4 Let a1,a2,a3∈Rdbe three points in weak general position with respect
to a polytope K and assume that HS(ai)=∅for all three. Then, for j ∈{0,...,d−3},
we have
˜
βj(bisK(a1,a2,a3)) =
3
i=1
˜
βj(HS(ai)) .
Proof Consider the same projection pr :Rd→Rd−1as before. Observe that, since
x∩HS(ai)is empty or contractible for every plane xparallel to pr, we have
HS(ai)≃π(HS(ai)) for i=1,2,3.
We now apply Alexander duality in the one-point compactification Sof int(pr(K)),
which is a sphere of dimension d−2. Alexander duality says that if Uis an open and
locally contractible subset of Sthen
˜
βj(U)=˜
βd−3−j(S\U).
In particular, if we let Ci=S\pr(HS(ai)) we have
3
i=1
˜
βj(pr(HS(ai))) =
3
i=1
˜
βd−3−j(Ci),
and
˜
βj3
i=1
pr(HS(ai))=˜
βd−3−j3
i=1
Ci.
Yet C1,C2and C3are pairwise disjoint except for the “point at infinity” of S, because
each point of int(pr(K)) lies in at least two of the sets pr(HS(ai)). Thus, 3
i=1Ciis the
topological wedge (or one-point sum) of C1,C2and C3, which makes the right-hand
sides of the two last equations coincide.
Remark 6 One may ask how complicated the Betti numbers ˜
βj(HS(ai)) in Theorem 4
can be. Equivalently, how complicated the topology of three point bisectors can be.
Such a bisector is (d−2)-dimensional, so the relevant Betti numbers are ˜
β0,..., ˜
βd−2.
The last one, ˜
βd−2, must vanish as ˜
βj(HS(ai)) =˜
βj(pr(HS(ai))), and the latter is an
open subset of Rd−2.But ˜
βd−3can be nonzero, as the following example shows.
Example 3 Let K=B3be the tropical unit ball, i.e., d=3. The three sites a=
(0,0,4,4),b=(−3,0,2,0)and c=(0,−3,0,2)lie in weak general position in
R4/R1. We describe each sector in terms of the facets whose relative interiors lie
in that sector. The facet Fij is the one at which coordinate iis minimized and jis
maximized. We obtain
H(a)=(F14,F23), H(b)=(F12,F13,F32,F42,F43),
H(c)=(F21,F24,F31,F34,F41).
123
Foundations of Computational Mathematics
aba
b
a
b
Fig. 5 Tropical bisectors for b−a=(−1,1,0),(−1,1,1
2)and (−1,1,1), respectively. The first two are
in weak general position but the last one is not. Only the middle one is in general position. The bisectors
are shown in black and the rest of the tropical hypersurface containing it in gray; see Proposition 4
The sector H(a)is disconnected; i.e., ˜
β0(H(a)) is nonzero. By Theorem 4bis(a,b,c)
is disconnected, too.
Remark 7 The results in this section and in Sect. 3.2 involve only weak general
position. While we keep assuming that Kis a polytope for simplicity, these results
generalize to an arbitrary convex body K. In that case Sis in weak general position if
the boundary ∂Kcontains no segment parallel to a difference a−bwith a,b∈S.
4 Classification of Tropical Bisectors of Two Points
4.1 Tropical Bisectors and Tropical Hypersurfaces
Intheclassicalcasethebisectoroftwopointsisadegeneratequadric,namelytheaffine
hyperplane perpendicular to the connecting line segment and which runs through the
midpoint. The tropical analog is more interesting.
Proposition 4 Let a,b∈Rd+1/R1be in weak general position. Then the homoge-
neous max-tropical Laurent polynomial
φ(a,b)=max max
i,j∈[d+1](xi−ai−xj+aj), max
k,∈[d+1](xk−bk−x+b)(6)
vanishes on the bisector bis(a,b). That is, the set bis(a,b)is contained in a max-
tropical hypersurface of degree d +1.
Proof Recall that a max-tropical (Laurent) polynomial vanishes if the maximum is
attained at least twice; see [22, §3.1]. First, we check that there are no duplicates
among the terms in the representation (6)ofφ(a,b). Assume the contrary, i.e., xi−
ai−xj+aj=xi−bi−xj+bjfor some i,j∈[d+1]. Then aj−ai=bj−bi,
which forces ej−ei,b−a=(bj−aj)−(bi−ai)=0. Thus b−ais parallel
123
Foundations of Computational Mathematics
to the facet of Bdwith normal vector ej−ei. This was explicitly excluded in our
assumption, and we arrive at the desired contradiction. We infer that the 2d(d+1)
terms are pairwise distinct.
Let x∈bis(a,b). This means that dist(a,x)=dist(b,x), and thus
max
i,j∈[d+1](xi−ai−xj+aj)=max
k,∈[d+1](xk−bk−x+b).
It follows that φ(a,b)vanishes at x.
The degree of the bisector tropical hypersurface can be read off any Laurent mono-
mial like xi−xjby adding x1+x2+···+xd+1, which yields the true monomial
2xi+k∈[d+1]−{i,j}xk. The latter has degree 2 +(d+1−2)=d+1.
Proposition4yieldsatrivialalgorithm tocomputetropicalbisectorsin weakgeneral
position: enumerate the maximal cells of the tropical hypersurface defined by (6) and
select those maximal cells that attain maxima in one monomial of type xi−ai−xj+aj
and one monomial of type xk−bk−x+b. This algorithm needs to go through the
(d4)choices of one monomial from the left and one from the right. This is worst
case optimal, as we will prove in Corollary 8that tropical bisectors can have (d4)
maximal cells.
Example 4 The labeling of the faces of a tropical bisector does not need to be unique
if aand bare not in weak general position. For instance, if b−a=(−1,1,0)then
bis(−+∗),(+−∗)(a,b)=bis(−++),(+−+)(a,b)
=bis(−++),(+−−)(a,b)=bis(−+−),(+−+)(a,b)
=bis(−+−),(+−−)(a,b)
is the only face; see Fig. 5(left).
4.2 The Bisection Fan
Normal equivalence of tropical bisectors is preserved by translation and scaling. In
particular the equivalence class of bis(a,b)is uniquely determined by the direction of
the vector b−a.Thebisection fan Fd
bis is the complete polyhedral fan in Rd+1/R1
whose relatively open cones are defined by “xand ylie in the same cone if and
only if bis(0,x)and bis(0,y)are normally equivalent”. Put differently, two points
a,b∈Rd+1/R1are in general position if and only if the difference b−alies in
a maximal cone of Fd
bis. In the rest of this section we show that Fd
bis is indeed a
polyhedral fan and give an explicit description of it.
Recall that an ordered partition or total preorder on a finite set Sis a partition of S
into non-empty parts together with a total order on the parts. If the parts are denoted
S1,...,Sk(in this order), we can write x≤ymeaning “x∈Siand y∈Sjfor some
i≤j”. In particular, for all x,y∈Swe have x≤y≤xif and only if xand ylie in
the same part.
Any real vector v=(v1,...,v
d+1)∈Rd+1induces an ordered partition S(v) of
[d+1]by putting together the coordinates that have the same value and ordering the
123
Foundations of Computational Mathematics
Fig. 6 The fans F(B3),F(A3), and the bisection fan F3
bop
groups according to their values. For example, the vector v=(3,1,6,4,6,3,1)of
length seven induces the partition ({2,7},{1,6},{4},{3,5})of the set {1,2,...,7}
into four parts. Note that the ordered partition S(v) is constant on the class v+R1.
Hence these ordered partitions are defined for points in the projective tropical torus
Rd+1/R1.
For v, w ∈Rd+1with S(v) =S(w) we have S(v +w) =S(v) and, moreover,
S(αv) =S(v) for any positive real α. That is to say, the stratification of Rd+1by
ordered partitions forms a complete polyhedral fan. In what follows we seek to refine
that fan by recording which part, or which gap between parts, contains the midvalue
μ(v) := 1
2max
i∈[d+1]vi+min
i∈[d+1]vi.
The bisected ordered partition of [d+1]induced by v∈Rd+1is the ordered
partition S(v) as defined above, together with the information of which (values of)
parts are smaller, equal or greater than the midvalue μ(v); see also [9]. Equivalently,
this is the ordered partition associated with the extended vector (v, μ(v)) ∈Rd+2.We
denote by Fd
bop the fan of bisected ordered partitions of dimension d.
Remark 8 The “finest” or “most generic” ordered partitions are the permutations, in
which each part is a singleton. Hence, the fan of ordered partitions equals the normal
fan of the permutahedron. This, in turn, coincides with the fan of regions in the braid
arrangement or Coxeter arrangement of type Ad, which consists of the hyperplanes
xxi=xjfor 1 ≤i<j≤d+1. We denote this fan F(Ad). It is intermediate
between the central fan of the tropical ball (which is coarser) and the fan of bisected
ordered partitions (which is finer):
F(Bd)≤F(Ad)≤Fd
bop ;
see Fig. 6for a visualization of the case d=3. Note that F(Ad)is also the fan of
weak general position: aand bare in weak general position if and only if b−alies
in a full-dimensional cell.
123
Foundations of Computational Mathematics
(−1,−1,1)
(0,−1,1)
(1,−1,1)
(1,−1,0)
(1,−1,−1)
(1,0,−1)
(1,1,−1)
(0,1,−1)
(−1,1,−1)
(−1,1,0)
(−1,1,1)
(−1,0,1)
b
b
b
a
Fig. 7 The bisection fan, Fd
bis,ford=2. The three vectors b−afor Fig. 5have been marked
Example 5 In d=2, the fans F(Ad)and F(Bd)coincide, they form the face fan of
the regular hexagon B2. The bisection fan Fd
bop is the barycentric subdivision of it; see
Fig. 7. Excluding permutations of the coordinates, and sign inversion, we infer that
there are three types of tropical bisectors in the plane, and these are shown in Fig. 5.
The type to the left is in weak general position but not in general position, the type
to the left is in general position, and the type to the right is not even in weak general
position.
Recall that the max-tropical line segment spanned by two points, aand b,istheset
[a,b]:=max(α1+a,β1+b)α, β ∈R⊂Rd+1/R1.
It is worth noting that the combinatorial types of tropical segments are classified by
the braid fan F(Ad);see[22, Prop. 5.11]. In this sense the fan of bisected ordered
partitions Fd
bop classifies the combinatorial types of “bisected tropical segments”:
Proposition 5 The bisected ordered partition of b−a contains the same information as
the combinatorial type of the tropical line segment [a,b]together with the information
of which part contains the midpoint.
Proof Suppose for simplicity that a,b∈Rd+1satisfy
b1−a1≤b2−a2≤... ≤bd+1−ad+1.(7)
Then [a,b]is the union of at most dordinary line segments, one for each subset of
coordinates between a strict inequality in (7). That is, the combinatorics of the tropical
123
Foundations of Computational Mathematics
segment is the same as the ordered partition of b−a. The midvalue μ(b−a)selects
one of the ordinary segments.
The goal of the rest of this section is to prove the following:
Theorem 5 We have Fd
bis =Fd
bop. That is, given a,b,a,b∈Rd+1/R1the polyhedra
bis(a,b)and bis(a,b)are normally equivalent if and only if b −a and b−ainduce
the same bisected ordered partition of [d+1].
4.3 Proof of Theorem 5
In (3) we defined the type (F−,F∗,F+)of a face Fof Bdor the corresponding face
cone in F(Bd). For a pair of faces, Fand G, this gives rise to the following labeling
partition of [d+1]:
L0:= (F−∩G−)∪(F+∩G+),
L+:= F+∩G∗∪F∗∩G−,
L−:= F−∩G∗∪F∗∩G+,
L+1:= F+∩G−,
L−1:= F−∩G+,
L∗:= F∗∩G∗.
(8)
As a first step in the Proof of Theorem 5, the following lemma characterizes when
bis(F,G)(a,b)is non-empty. Recall that this is the case if and only if there is a tropical
ball touching aand bat faces Fand G, respectively.
Lemma 7 Let F and G be a fixed pair of faces of Bdwith the labeling partition defined
as in (8). Further let a,b∈Rd+1/R1. Then the set bis(F,G)(a,b)is not empty if and
only if there exist γ∈Rand δ∈[0,∞)such that the following conditions are
satisfied:
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎩
(b−a)i=γif i ∈L0,
(b−a)i∈[γ,γ +δ]if i ∈L+,
(b−a)i∈[γ−δ, γ]if i ∈L−,
(b−a)i=γ−δif i ∈L−1,
(b−a)i=γ+δif i ∈L+1,
(b−a)i∈[γ−δ, γ +δ]if i ∈L∗.
(9)
Proof Let us assume that the face of the tropical bisector bis(a,b)defined by (F,G)is
non-empty. Then there is a point xsuch that dist(a,x)=dist(x,b)=δand a−x∈F
as well as b−x∈G.Wesetγa=mini∈[d+1](ai−xi)and γb=mini∈[d+1](bi−xi).
The possible values for the coordinates of a−xand b−xare
⎧
⎨
⎩
(a−x)i=γa+δif i∈F−,
(a−x)i=γaif i∈F+,
(a−x)i∈[γa,γ
a+δ]if i∈[d+1]\(F−∪F+)
(10)
123
Foundations of Computational Mathematics
and
⎧
⎨
⎩
(b−x)i=γb+δif i∈G−,
(b−x)i=γbif i∈G+,
(b−x)i∈[γb,γ
b+δ]if i∈[d+1]\(G−∪G+),
(11)
for some δ≥0. Setting γ=γb−γathe above translates into (9).
For the converse, note that going from (10) and (11)to(9) is the Fourier-Motzkin
elimination of the variables xi. Therefore, any γand δ≥0 which are feasible for
(9) can be lifted to a solution of (10) and (11). That is to say, we can set γa=0 and
γb=γ, and the conditions in (10) and (11) yield a point x∈bis(F,G)(a,b).
Proposition 6 Let F and G be a fixed pair of faces of Bd. Then the set
C:= b−aa,b∈Rd+1/R1with bis(F,G)(a,b)=∅
(12)
is both a polyhedral cone and a tropical cone, although perhaps not a tropical poly-
hedral cone.
Proof Let a,a,b,b∈Rd+1/R1with bis(F,G)(a,b)and bis(F,G)(a,b)both non-
empty. Since bis(F,G)(a,b)=∅, by Lemma 7, there are scalars γand δsatisfying
the conditions (9). Likewise there are certificates γand δfor bis(F,G)(a,b)=
∅. By linearity of the conditions (9) it follows that γ+γand δ+δcertify that
bis(F,G)(a+a,b+b)=∅: for instance, we have (b+b−a−a)i=γ+γfor
i∈L0=(F−∩G−)∪(F+∩G+). Since clearly αc∈Cfor all c∈Cand α≥0we
conclude that Cis an ordinary cone. This cone is polyhedral as it is defined in terms
of the finitely many linear conditions (9).
A similar argument shows that Cis also closed with respect to taking arbitrary
(max,+)-linear combinations: for instance, with the above notation we have max((b−
a)i,(b−a)i)=max(γ, γ )for i∈L0. This shows that Cis a tropical cone.
Corollary 7 The bisection fan of tropical bisectors is a classical polyhedral fan, and
a tropical (perhaps not tropical polyhedral) fan.
Proof We know that the feasibility region of a face (F,G)is a tropical and classical
polyhedral cone. Finite intersections of these cones are again tropical cones, classical
cones, and polyhedral cones. Therefore, the feasibility region of a normal equivalence
class, which is the intersection of the cones of its non-empty faces, is again a tropical
and classical polyhedral cone. Hence, the whole fan has this structure.
The following shows one direction of Theorem 5, namely, Fd
bis is coarser than Fd
bop.
Lemma 8 Let F,G∈F(Bd). Then, whether bis(F,G)(a,b)is empty or not, for each
a,b∈Rd+1/R1depends only on the bisected ordered partition of b −a.
Proof Consider the partition of [d+1]into six sets L0,L+,L−,L+1,L−1,L∗defined
in (8). We want to show that feasibility of the system (9) for a given aand bdepends
123
Foundations of Computational Mathematics
only on the bisected ordered partition of b−a. Without loss of generality we assume
a=0 and b1≤b2≤···≤bd+1as in (7).
Let μ(b):= 1
2(bd+1+b1)=1
2dist(0,b)+b1be the midvalue of b−0 and
m=max(0+μ(b)1,b)the midpoint of the segment [0,b]. In particular, dist(0,m)=
dist(m,b)=1
2dist(0,b).
We distinguish three cases, depending on whether both, none, or exactly one of
L+1and L−1are empty.
Claim I: Suppose L+1∪L−1=∅.Then, (9)is feasible if and only if there are
k≤with
L−⊆{1,...,k}L0⊆{k+1,...,},L+⊆{+1,...,d+1}.(I.1)
Indeed, in this case feasibility of (9) is equivalent to feasibility of
⎧
⎪
⎨
⎪
⎩
γ≥bifor i∈L−,
γ=bifor i∈L0,
γ≤bifor i∈L+,
(13)
which implies the ordered partition to satisfy (I.1). Conversely, if the ordered partition
satisfies (I.1), then let γbe chosen to satisfy (13) and let δ≥min(γ −b1,bd+1−γ).
This yields a feasible solution to (9). In other words, in this case we can tell if Cis
empty or not by just looking at the the ordered partition of b; the relative position of
the midpoint is irrelevant.
Claim II: Suppose L+1=∅=L−1.Then,(9)is feasible if and only if, in addition
to (I.1), we have
bii∈L+1={bd+1},(II.1)
bi≤μ(b)for i∈L0∪L−,(II.2)
|bii∈L0|≤1.(II.3)
If (I.1), (II.1), (II.2), and (II.3) hold, take γ=max bii∈L0∪L−∪{1}and
δ=bd+1−γ.
Conversely, if (γ, δ) is feasible for (9) then γ+δ=bi=bd+1for all i∈L+1.In
particular, bis(F,G)(a,b)is empty unless {bi|i∈L+1}={bd+1}is a singleton. Since
the coefficients of bare in ascending order, it follows that
γ+δ=bd+1(14)
and bi=bd+1for all i∈L+1. This shows that (II.1) holds. Now the constraints of
(9) translate into (13) as in the previous case, which implies (I.1). Additionally
γ−δ≤b1.(15)
123
Foundations of Computational Mathematics
Adding (14) and (15) now yields
γ≤1
2(b1+bd+1)=μ(b),
which, by (13), gives (II.2). Finally, (II.3) follows from the fact that the only possible
value in bii∈L0is γ.
The case where L−1=∅and L+1=∅is analogous.
Claim III: Suppose L+1=∅= L−1.Then,(9)is feasible if and only if
bii∈L−1={b1}bii∈L+1={bd+1},(III.1)
bi≤μ(b)for i∈L−,bi=μ(b)for i∈L0,bi≥μ(b)for i∈L+.(III.2)
Indeed, in this case the only candidate solution for (9)isγ=μ(b)=(bd+1+b1)/2
and δ=(bd+1−b1)/2. This is a solution or not depending only on whether Eqs. (III.1)
and (III.2) are satisfied.
The following gives the other direction of Theorem 5:Fd
bis refines Fd
bop.
Lemma 9 Let a,b,a,b∈Rd+1/R1be two pairs of points. If the bisected ordered
partitions of b −a and b−aare not the same, then there is a pair of faces F,G∈
F(Bd)such that exactly one of bisF,G(a,b)or bisF,G(a,b)is empty.
Proof As before, we assume without loss of generality that a=a=0. We know that
the bisected ordered partitions of band bare different. Our goal is to find a pair of
faces (F,G)that lies in one and only one of the bisectors. We do this in three cases,
depending on the difference between the bisected ordered partitions
Case I: Suppose that
i∈[d+1]bi=max
jbj= i∈[d+1]b
i=max
jb
jor
i∈[d+1]bi=min
jbj= i∈[d+1]b
i=min
jb
j.
Without loss of generality, there is an index isuch that biis maximum and b
iis not,
or biis minimum and b
iis not. Let Fbe the face with
F+=i∈[d+1]bi=max
jbj,F−=i∈[d+1]bi=min
jbj,
and let G=−F. This choice makes
L+1=F+,L−1=F−,L∗=F∗,L−=L+=L0=∅.
123
Foundations of Computational Mathematics
The cell bisF,G(a,b)is not empty by Lemma 7, since the following is a solution for
(9):
γ=1
2(max
i∈[d+1]bi+min
i∈[d+1]bi),
δ=1
2(max
i∈[d+1]ai−min
i∈[d+1]bi)=1
2dist(a,b).
However, bis(F,G)(a,b)is empty: in order for it not to be empty we would need
i∈[d+1]b
i=min
jb
j⊂F−,i∈[d+1]b
i=max
jb
j⊂F+.
Case II: Suppose that b and bhave exactly the same maxima and minima but
the ordered partitions of b and bdo not coincide. That is, there is a pair of indices,
i,j∈[d+1]\{1,d+1}such that bi≥bjbut b
i<b
j.
We may assume that 1 and d+1 are a minimum and a maximum, respectively, of
both band b.LetFbe the face with F+={d+1}and F−={1}.LetGbe the face
with G+={i}, and G−={j}. Then, (8)gives
L+={d+1,j},L−={1,i},
L∗=[d+1]\(L+∪L−), L−1=L+1=L0=∅.
Then, bisF,G(a,b)is not empty since γ=(bi+bj)/2, and δ=dist(a,b)is a solution
of (9). However, the system for bis infeasible, since b
i<b
j. Thus, bisF,G(a,b)is
empty.
Case III: Suppose that b and bhave exactly the same maxima and minima and
the same ordered partitions but the midvalue does not coincide.
As before, we assume without loss of generality that 1 and d+1 are a minimum and
amaximum,respectively,ofbothbandb. Then, thereisanindexi∈[d+1]\{1,d+1}
such that μ(b)≤bibut μ(b)>b
i(or vice-versa, but that would give an equivalent
case).
In this case, we let Fand Gbe the faces with F+={d+1},F−={1},G+={1}
and G−={i}. These faces produce
L+={d+1,i},L−1={1},
L∗=[d+1]\(L+∪L−1), L−=L+1=L0=∅.
Then, bisF,G(a,b)is not empty since γ=μ(b),δ=dist(a,b)/2 is a solution of (9)
for b
However, the system for bis infeasible. This is because (9) specifies that γ+
δ≥b
d+1, and γ−δ=b
1. Adding them together and dividing by two we get
γ≥(b
1+b
d+1)/2=μ(b). We also need by (9) and i∈L+that γ≤b
i. Then,
μ(b)≤b
i, which contradicts our assumption.
Corollary 8 The tropical bisector of two points in general position has (d4)maximal
cells.
123
Foundations of Computational Mathematics
Proof The upper bound is trivial, each maximal cell corresponds to a choice of a
pair of facets (F,G)from the tropical ball. For the lower bound, assume without
loss of generality that a=0 and b1<b2<··· <bd+1. Then, for each choice of
i,j,k,∈{1,...,d+1}, all different and with max{j,}<min{i,k},letF+={i},
F−={j},G+={k},G−={}. By Claim 1 in the Proof of Lemma 8the set
bis(F,G)(a,b)is not empty. Since aand bare in general position and Fand Gare
facets of Bd,wehavedimbis
(F,G)(a,b)=d−1. There are 4d+1
4ways of choosing
such {i,j,k,}.
4.4 The Structure of Tropical Voronoi Regions
Apolytrope is an ordinary polytope which is also convex in the tropical sense (with
respect to min and max simultaneously); see [17]. These are precisely the ordinary
polytopes whose facets normals are roots of type Ad, i.e., ei−ejfor i= j;they
generalize the “alcoved polytopes” of Lam and Postnikov [20]. Here we relax this
notion by also calling a not necessarily bounded ordinary polyhedron a polytrope if its
facets normals are roots of type Ad; this was called a “weighted digraph polyhedron”
in [18].
The tropical unit ball Bdis a polytrope. But a more important example for us are
the polytropes Q=a∈S(a+Fa), where Fa∈Bdfor each a∈S. Recall from Sect. 3
that in such a Qbisectors of subsets of Sagree with affine subspaces. Thus:
Lemma 10 For each polytrope Q as above and a ∈S, the set Q ∩Vor S(a)is the
intersection of Q with ordinary affine halfspaces with facet normal ei−ej−ek+e,
where i and j are fixed.
Proof Let iand jbe the coordinates maximized and minimized in Fa, respectively.
For each b∈S\a, the condition for xto be closer to athan to bis that xi−ai−xj+
aj≤xk−bk−x+b, where kand are the coordinates corresponding to Fb;see
Proposition 4.
We call the intersection of a (possibly unbounded) polytrope with ordinary affine
halfspaces with facet normal ei−ej−ek+e, where iand jare fixed, a semi-polytrope
of type (i,j). A semi-polytrope in Rd+1/R1∼
=Rdhas at most 2d+1
2facets, since
there are at most (d+1)dvectors ei−ej−ek+efor k= and fixed (i,j),plus
the (at most) (d+1)dfacets of a polytrope.
AsetX⊂Rd+1/R1∼
=Rdis star convex with center cif for any point x∈X
the ordinary line segment [c,x]is contained in X. Clearly any convex set is star
convex, but the converse does not hold. Star convex sets are contractible. Despite the
many differences to Euclidean Voronoi diagrams, the following result expresses a key
similarity.
Theorem 6 Let S ⊂Rd+1/R1be a finite set in weak general position. Then each trop-
ical Voronoi region of S is the star convex union of finitely many (possibly unbounded)
semi-polytropes.
123
Foundations of Computational Mathematics
Fig. 8 Tropical Voronoi diagram of five points in R3/R1. The decomposition of Voronoi regions into
semi-polytropes is shown by dashed lines
Proof That Voronoi regions for polyhedral norms are star-convex is a well-known
fact (see [4, p. 133] or [23, p. 127]), which follows for example from Theorem 2.By
Lemma 10,Vor
S(a)decomposes as finitely many semi-polytropes, by intersecting it
with the individual polyhedra Q=a∈S(a+Fa), for all choices of {Fa}a∈S.
Semi-polytropes are not necessarily tropically convex, and this entails that the
regions of a tropical Voronoi diagram are not necessarily tropically convex either; see
Fig. 8for an example. The tropical torus Rd+1/R1is compactified by the tropical
projective space TPd; the latter is the max-tropical convex hull of the d+1max-
tropical unit vectors
(0,−∞,−∞,...,−∞), (−∞,0,−∞,...,−∞), . . . , (−∞,−∞,...,−∞,0).
In this way, TPdmay be seen as an infinitely scaled tropical unit ball, which is a
polytrope; see [18, §3.5]. Similarly for arbitrary (semi-)polytropes the line between
bounded and unbounded is blurred in the compactification.
5 Computing Tropical Voronoi Diagrams
We will discuss several algorithms. Some of these methods are similar to their clas-
sical Euclidean counterparts, others rely on tailored data structures, which are based
on Theorem 6. For the complexity analysis of our algorithms we will consider the
dimension as constant.
123
Foundations of Computational Mathematics
5.1 The Planar Case
There are several methods for computing Euclidean Voronoi diagrams in R2with
the optimal time complexity O(nlog n)and linear space; see [7, §7.2]. This agrees
with the situation for planar tropical convex hull computations; see [16, §5]. Chew
and Drysdale [6] gave a divide-and-conquer algorithm with the same complexity for
planar Voronoi diagrams with respect to arbitrary norms. Here we sketch a tropical
analog of Fortune’s beach line algorithm [10]; see also [27].
Suppose that we are given a set Sof nsites in R3/R1. In view of Theorem 6
the tropical Voronoi diagram of Sgives rise to a planar graph where vertices are
circumcenters of triples of points in S, edges are two point bisectors, and faces are
Voronoi regions. We can make this planar embedding piecewise linear by subdividing
each bisector into at most five segments; see Fig. 5. The relevant data structure, as in
the classical setting, is a doubly-connected edge list which requires O(n)space; see
[7, §2.2].
The beach line algorithm is based on a line sweep. The tropical sweep line at time t
in R3/R1is the set L(t)=(0,t,0)+R(0,0,1)+R1. Note that L(t)is an ordinary
line which is also tropically convex (with respect to min and max). For an arbitrary
point xwe call the set
P(x,t)=a∈R3/R1dist(x,a)=dist(x,L(t))
the parabola spanned by x and L(t); here dist(x,L(t)) =min{dist(x,y)|y−
(0,t,0)∈R(0,0,1)+R1}. This is a 1-dimensional polyhedral complex, which
is homeomorphic with L(t)via orthogonal projection, consisting of five segments.
We will assume that our set Sof sites is in general position and hence, in particular,
each sweep line contains at most one site. A point a=(a1,a2,a3)is said to have been
visited by the sweep line L(t)if a2−a1≤t.
The beach line B(t)of Sat time tis formed by the points (b1,b2,b3)which lie on
a parabola P(s,t)for a visited point ssuch that b2−b1is maximal among all such
points for a fixed value b3−b1. That is, the beach line is formed by the right-most
points on the parabolas spanned by the visited points and the sweep line; see Fig. 9.
So B(t)is a union of parabolic arcs; it is easy to see that each parabola contributes at
most two arcs to the beach line at any time. Like a single parabola also the beach line
B(t)is homeomorphic to L(t)via orthogonal projection. In the portion of R3/R1left
to B(t)the tropical Voronoi diagram of Sis known at time t.
Observation 7 The beach line is a polygonal line with O(n)segments.
The actual algorithm works as in the classical case. We maintain a priority queue
of site events (when the sweep line visits a site) and circle events (when there is a
candidate for a new vertex of the tropical Voronoi diagram). The total number of
events is linear in n. As in the classical case, it is possible to relax the condition on
general position by means of symbolic perturbation.
Theorem 8 The beach line algorithm computes a tropical Voronoi diagram of n sites
in R3/R1in O(nlog n)time and O(n)space.
123
Foundations of Computational Mathematics
v
(0,0,0)
(0,1,3)
(0,−3,−1)
(0,−1,−3)
(0,2,−1)
v
(0,0,0)
(0,1,3)
(0,−3,−1)
(0,−1,−3)
(0,2,−1)
Fig. 9 The beach line and the sweep line, for t=1 (left) and t=3 (right)
For the output we can choose, with the same complexity, between an abstract planar
graph (encoding Vor(S)topologically) and its piecewise linear embedding resulting
from Theorem 6.
5.2 Polytrope Partitions
Let S⊆Rd+1/R1be a finite set of sites. From Theorem 6we know that the tropical
Voronoi diagram can be described in terms of (semi-)polytropes. For the definition
and basic facts on polytropes, see Sect. 4.4 and [17]. The following takes inspiration
from the trapezoid map data structure; see [7, §6].
Definition 2 Apolytrope partition for Sis a finite collection Cof (perhaps unbounded)
non-degenerate polytropes with disjoint interiors, covering Rd+1/R1, such that:
1. each facet-defining hyperplane of any cell in Clies in the hyperplane arrangement
S+Ad.
2. for each cell Pin Cand site a∈Sthe restricted Voronoi region VorS(a)∩Pis
contained in a maximal cone a+Fof a+F(Bd).
Avalid labeling for Cassigns to each cell P∈Ca (partial) matching LC(P)of
S×F(Bd)containing
(a,F)∈S×F(Bd)(a+F)∩P∩Vor S(a)=∅
.
The distance function x→ dist(x,a)to a fixed site ais piecewise linear, as it is
linear in each translated cone a+Ffor F∈F(Bd). Polytrope partitions are designed
to exploit this fact, so that the distances to the relevant sites in each cell are linear. In
particular:
Observation 9 Let Pbe a cell in a polytrope partition Cfor S. Then for all x∈Pwe
have
dist(x,S)=min
a∈SλFa(x−a)(16)
where λFais the linear function defined by restricting the distance to aon some
maximal cone a+Faof a+F(Bd)which contains VorS(a)∩P. Thus computing
123
Foundations of Computational Mathematics
the restriction of Vor(S)to the polytrope Pamounts to finding the regions of linearity
of the tropical polynomial mina∈SλFa(x). The latter can be obtained via an ordinary
dual convex hull computation.
Note that the maximal cone Fain the above is irrelevant if VorS(a)∩P=∅, and
it is unique, by axiom (2), if VorS(a)∩P=∅. If the polytrope partition is equipped
with a valid labeling, then this tells us the choice of the right cone Fafor each site, if
it exists.
The following shows that polytrope partitions exist.
Example 6 The braid arrangement Adconsists of the d+1
2ordinary hyperplanes
{x|xi=xj}, where i= j. This gives rise to the standard polytrope partition S +Ad,
which is finer than any other polytrope partition for S;Fig.8shows an example for
d=2. This construction occurs in planar tropical convex hull algorithms; see [16,
Figure 3].
Andfinally,thefollowinglemmashowsthatvalid labelingsexistforeverypolytrope
partition, if the sites Sare in weak general position:
Lemma 11 Let Cbe a polytrope partition for S. If S is in weak general position then
there is a valid labeling of C. Moreover, for d considered constant, a labeling of each
polytropal cell has constant size, and it can be computed in O(n)time.
Proof Suppose that a valid labeling does not exist for some cell P. Either the set of
pairs in (2) matches two cones with the same site, or matches two sites with the same
cone of F(Bd). The former cannot happen since Pis full-dimensional and the cones
in F(Bd)only intersect in lower-dimensional polyhedral cones.
Then there are sites a,b∈Sand a maximal cone F∈F(Bd)such that the sets
(a+F)∩P∩Vor S(s)and (b+F)∩P∩Vor S(t)both are non-empty.
With the notation of (16)wehaveλFa=λFb; and we shortly write λ. Since
the sites are in weak general position, we may assume that λ(b)>λ(a). Picking
y∈(b+F)∩P∩Vor S(b)yields
dist(y,b)≥λ(b)>λ(a)≥dist(y,S),
where the last inequality follows from (16). The resulting inequality dist(y,b)>
dist(y,S)implies that y/∈Vor S(b), which is a contradiction. Hence a valid labeling
does exist.
To compute such labeling, we iterate through all the sites. For each site a,the
candidate facet of Fa∈F(Bd)is known by definition of the polytrope partition. To
check if (a,Fa)is a labeling candidate, we need to determine if (a+Fa)∩P∩Vor S(a)
is empty or not. This amounts to solving a linear program that has constant size (as d
is a constant). It follows that the entire labeling can be computed in O(n)time.
We aim at a first algorithm for computing a tropical Voronoi diagram in arbitrary
dimension. This will employ the standard polytrope partition from Example 6.
123
Foundations of Computational Mathematics
Lemma 12 If S is in weak general position and has size n then the trivial polytrope
partition has
(d+1)d−1nd+O(nd−1)
maximal cells, if we consider d a fixed constant.
Proof Pick a generic direction v∈Rd+1/R1. The cells of the polytrope partition
that are bounded in the direction of vare in a one-to-one correspondence with the
vertices of the arrangement, by associating each polytrope with the optimum of the
linear program maximizing vTx. Since the number of vertices equals
(d+1)d−1nd−n(d+1)d−1−1,
by Cayley’s formula, it suffices to show that the number of unbounded cells is in
O(nd−1), as the bases of Adcorrespond to spanning trees in the complete graph with
dvertices. The unbounded cells intersect a hyperplane, H, normal to vthat is far
enough in the vdirection. The cells intersecting Hare the same as the cells in the
restricted hyperplane arrangement, which is a (d−1)-dimensional arrangement with
N=d+1
2nhyperplanes. The number of such cells is known to be in ONd−1,
which agrees with Ond−1as Ndepends linearly on n.
Remark 9 (Standard polytrope partition algorithm) This directly yields a first algo-
rithm for computing a tropical Voronoi diagram of nsites in Rd+1/R1in O(nd+1)
time, as follows: First, we sort Salong each of the (d+1)
2directions ei+ej,
in O(nlog n)time. As in the Proof of Lemma 12 we pick a generic direction
v∈Rd+1/R1. We can compute the vertices of the hyperplane arrangement Ad+S
in time O(nd)by enumerating all d-sets of independent directions, which can be
derived from the the oriented spanning tree of Kd+1, in constant time. For each of the
ddirections we choose an index i∈[n].
Next we perturb each such vertex pby a small multiple of −v, and we collect
the intersection of bands of contiguous parallel hyperplanes of Ad+Sthat contain
the perturbed point. This can be done in time O(log n)for each direction. In this
way, we find those cells which are bounded in the direction of this particular vin
linear output-dependent time. We repeat the same procedure for a set of directions
v1,...,v
d+1which positively span the entire space Rd+1/R1. Each polytropal cell
will be bounded in at least one of these directions, and thus their enumeration is still
in O(nd)for dfixed.
Then, for each polytrope P, we compute a corresponding labeling in time O(n),
by Lemma 11. Therefore, we can compute the standard polytrope partition, including
labels, in time O(nd+1)for fixed d. The tropical Voronoi diagram in each cell is
an ordinary dual convex hull problem of constant size. This computation splits each
polytrope in the partition into semi-polytropes. The convex hull problem can be solved
in constant time, and hence this algorithm takes O(nd+1)time, if dis considered a
fixed constant.
We implemented this procedure in polymake [11], version 3.6.
123
Foundations of Computational Mathematics
Question 1 In the plane R3/R1, we believe that ideas similar to the “trapezoidal maps”
used in point location, see [7, §6.1], should yield polytrope partitions of linear size
but we did not work out the details. More generally: Is there a polytrope partition of
complexity better than (nd)in arbitrary dimension? One could hope for something
in O(nd/2), which is the worst-case complexity of Euclidean Voronoi diagrams.
5.3 An O(ndlog n)Randomized Incremental Algorithm in Rd+1/R1
We can improve the algorithm from Remark 9by constructing a polytrope partition
incrementally. The idea is to update an existing polytrope partition by including a new
point and to employ randomization to improve the efficiency. Moreover, we will also
produce a coarser polytrope partition than the standard one, but only by a constant in
d.
A key ingredient is a new data structure that we call a polytrope tree. Throughout
we assume that the set Sof nsites forms a subset of Rd+1/R1in general position.
We fix the polytrope partition C:= S+F(Bd), which is coarser than the standard
polytrope partition but only by a factor which is constant in d; see Example 6.
Definition 3 Apolytrope tree for Sis a (rooted) tree Tsuch that
1. for each leaf there is a polytropal cell P() of C;
2. for each interior node ithere is a site a(i)∈Sand a polytrope P(i).
These satisfy the following consistency conditions:
– for the root node rof Twe have P(r)=Rd+1/R1, which may be seen as an
unbounded polytrope;
–themap→ P() is a bijection between the set of leaves of Tand the set of
polytropes in C;
–themapi→ a(i)is a surjection from the interior nodes onto the set S;
–ifiis an interior node with children c1,...,ck, then P(c1),...,P(ck)form the
maximal cells of (a(i)+F(Bd)) ∩P(i).
It is easy to construct a polytrope tree for S, and its purpose is to speed up the
computation of a valid labeling. This will reduce the algorithmic complexity from
O(nd+1)to O(ndlog n).
For the incremental update to insert a new site b/∈Swe maintain a stack of
unvisited nodes in a given polytrope tree for and process it as follows:
– the stack is initialized with the root node r;
– we remove the top node qfrom the stack unless it is empty;
–ifqis an interior node such that P(q)intersects more than one maximal cone of
s+F(Bd), then we push the children of qonto the stack ;
–ifqis a leaf such that P() intersects more than one maximal cone of p+F(Bd),
then we create the intersections of P() with s+F(Bd)as new leaves, which now
become children of q, and we set a(q)←b.
Note that an interior node qwith P(q)contained in a unique maximal cone of a+
F(Bd)is kept unchanged, and its children will not be visited. The following is the
essential part of the complexity analysis.
123
Foundations of Computational Mathematics
Proposition 7 Let T be a polytrope tree created in the way explained above, where
the n sites in S are processed in uniformly random order. Then the expected height of
T is of order O(log n), if d is considered a fixed constant.
Proof Let Pbe a polytrope in the polytrope partition C(S). For each ordering π:
[n]→Sof Swe have a polytrope tree T(S,π)with Pas a leaf. By induction on n
we will show:
E[hT(S,π)(P)]≤d(d+1)
n
i=1
1
i∈O(log n), (17)
wheretheexpectation E[·] istakenuniformlyoveralln!orderingsof S,andhT(S,π)(P)
is the depth of the leaf of Pin T(S,π).
We proceed by backwards analysis. Let S⊂Sbe the subset of sites that lie in
some facet-defining hyperplane of P. Since Phas at most d(d+1)facets and (by
general position) their corresponding hyperplanes contain each exactly one point of
S,wehave|S|≤d(d+1). Thus, the probability that the height hT(P)increases in
the last insertion is at most d(d+1)/n. Since the increase is by exactly one, we have
E[hT(S,π)(P)]≤E[hT(S\π(n),π[n−1])(P)]+d(d+1)
n,
where Pis the polytrope containing Pin the polytrope partition before the last
insertion. By induction hypothesis
E[hT(S\π(n),π[n−1])(P)]≤d(d+1)
n−1
i=1
1
i.
The last two formulas give Eq. (17).
Corollary 9 The above method constructs a polytrope tree for the polytrope partition
S+F(Bd)in expected time O(ndlog n)and space O(nd), for d constant.
Proof The algorithm that inserts a new site ainto the tree only visits nodes that are
above some leaf requiring an update. For each such leaf the polytrope P() intersects
one of the d(d+1)hyperplanes in a+Ad. This implies that there are O(nd−1)of
them. Since the expected depth of every leaf is O(log n)it requires expected time
O(nd−1log n)for inserting a. Hence the total complexity for nsites amounts to
O(ndlog n).
In order to compute the tropical Voronoi diagram, we also need to compute the
labeling of this polytrope partition. The naive way is to compute the labeling for each
leaf as we did in Remark 9.
Aslight improvement is tocomputethelabelingduringthedepth-first-search(DFS)
exploration of the tree at each insertion of a new site. But in this way, even if an interior
nodeiscompletely containedinonlyone coneofthefana+F(Bd),we needtodescend
123
Foundations of Computational Mathematics
to its subtree in order to update the labels. This would slow the algorithm down to
(nd+1)because each insertion will have to iterate through all the leaves.
A better way is to compute the labeling lazily. To this end we equip each interior
node iwith a partial labeling LC(i). With each new insertion, we proceed as we just
explained, but we do not cascade down the label updates. Only once all sites in Shave
been inserted we cascade the partial labels, updating them in DFS order. This takes
O(ndlog n)time to compute the polytropes and the lazy labelings, plus O(nd)time to
cascade the lazy labelings down in the tree, for a total time complexity of O(ndlog n)
time. This gives our final result.
Theorem 10 There is a randomized incremental algorithm for computing tropical
Voronoi diagrams of n sites in Rd+1/R1in general position with expected time com-
plexity O(ndlog n)and space complexity O(nd), for d constant.
Acknowledgements We thank Günter Rote and three anonymous referees for useful comments on a first
version of this paper. Especially, one referee brought the reference [3] to our attention.
Funding Open Access funding enabled and organized by Projekt DEAL.
Open Access ThisarticleislicensedunderaCreativeCommonsAttribution4.0InternationalLicense,which
permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give
appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence,
and indicate if changes were made. The images or other third party material in this article are included
in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If
material is not included in the article’s Creative Commons licence and your intended use is not permitted
by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the
copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
References
1. Daniele Alessandrini, Logarithmic limit sets of real semi-algebraic sets,Adv.Geom.13 (2013), no. 1,
155–190. MR 3011539.
2. Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, and Michael Joswig, Log-barrier interior
point methods are not strongly polynomial,SIAMJ.Appl.AlgebraGeom.2(2018), no. 1, 140–178.
3. Omid Amini and Madhusudan Manjunath, Riemann-Roch for sub-lattices of the root lattice An, Elec-
tron. J. Combin. 17 (2010), no. 1, Research Paper 124, 50. MR 2729373.
4. Franz Aurenhammer, Rolf Klein, and Der-Tsai Lee, Voronoi diagrams and Delaunay triangulations,
World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2013. MR 3186045.
5. Matthew Baker and Serguei Norine, Riemann-Roch and Abel-Jacobi theory on a finite graph,Adv.
Math. 215 (2007), no. 2, 766–788. MR 2355607.
6. L. Paul Chew and Robert L. Scot Dyrsdale III, Voronoi diagrams based on convex distance functions,
Proceedings of the first annual symposium on Computational geometry, ACM, 1985, pp. 235–244.
7. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Computational geometry,
third ed., Springer-Verlag, Berlin, 2008, Algorithms and applications. MR 2723879.
8. Jules Depersin, Stéphane Gaubert, and Michael Joswig, A tropical isoperimetric inequality,Sém.
Lothar. Combin. – FPSAC 2017 – 78B (2017), Art. 27, 12. MR 3678609.
9. Mike Develin, The moduli space of n tropically collinear points in Rd, Collect. Math. 56 (2005), no. 1,
1–19. MR 2131129.
10. Steven Fortune, A sweepline algorithm for Vorono˘ı diagrams, Algorithmica 2(1987), no. 2, 153–174.
MR895442 (88e:68101).
11. Ewgenij Gawrilow and Michael Joswig, polymake:a framework for analyzing convex polytopes,
Polytopes—combinatorics and computation (Oberwolfach, 1997), DMV Sem., vol. 29, Birkhäuser,
Basel, 2000, pp. 43–73. MR1785292 (2001f:52033).
123
Foundations of Computational Mathematics
12. Chan He, Horst Martini, and Senlin Wu, On bisectors for convex distance functions, Extracta Math.
28 (2013), no. 1, 57–76. MR 3135681.
13. Christian Icking, Rolf Klein, Ngo
.c-Minh Lê, and Lihong Ma, Convex distance functions in 3-space are
different, Fund. Inform. 22 (1995), no. 4, 331–352, Computational geometry (San Diego, CA, 1993).
MR 1360951.
14. ChristianIcking,RolfKlein, Ngoc-Minh Lê, Lihong Ma, and Francisco Santos, On bisectors for convex
distance functions in 3-space, CCCG, (1999).
15. Philipp Jell, Claus Scheiderer, and Josephine Yu, Real tropicalization and analytification of semialge-
braic sets, Int. Math. Res. Not. IMRN (2020), Published online: 29 May 2020.
16. Michael Joswig, Tropical halfspaces, Combinatorial and computational geometry, Math. Sci. Res. Inst.
Publ., vol. 52, Cambridge Univ. Press, Cambridge, 2005, pp. 409–431. MR2178330 (2006g:52012).
17. Michael Joswig and Katja Kulas, Tropical and ordinary convexity combined, Adv. Geometry 10 (2010),
333–352.
18. Michael Joswig and Georg Loho, Weighted digraphs and tropical cones, Linear Algebra Appl. 501
(2016), 304–343.
19. J. J. Kosowsky and Alan L. Yuille, The invisible hand algorithm: Solving the assignment problem with
statistical physics, Neural Networks 7(1994), no. 3, 477–490.
20. Thomas Lam and Alexander Postnikov, Alcoved polytopes. I, Discrete Comput. Geom. 38 (2007),
no. 3, 453–478. MR2352704.
21. Anthea Monod, Bo Lin, Ruriko Yoshida, Qiwen Kang, Tropical geometry of phylogenetic tree space:
a statistical perspective, (2020), Preprint arXiv:1805.12400v6
22. Diane Maclagan and Bernd Sturmfels, Introduction to tropical geometry, Graduate Studies in Mathe-
matics, vol. 161, American Mathematical Society, Providence, RI, 2015. 3287221
23. Horst Martini and Konrad J Swanepoel, The geometry of Minkowski spaces–a survey. part ii, Exposi-
tiones mathematicae 22 (2004), no. 2, 93–144.
24. Grigory Mikhalkin, Enumerative tropical algebraic geometry in R2,J.Amer.Math.Soc.18 (2005),
no. 2, 313–377. 2137980 (2006b:14097).
25. David Speyer and Bernd Sturmfels, The tropical Grassmannian,Adv.Geom.4(2004), no. 3, 389–411.
MR2071813 (2005d:14089)
26. Rade T. Živaljevi´c, Topological methods in discrete geometry, Handbook of Discrete and Computa-
tional Geometry (Csaba D. Tóth, Jacob E. Goodmann, and Joseph O’Rourke, eds.), CRC Press, 2018,
3rd edition.
27. Peter Widmayer, Ying-Fung Wu, and Chak-Kuen Wong, On some distance problems in fixed orienta-
tions, SIAM Journal on Computing 16 (1987), no. 4, 728–746.
Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps
and institutional affiliations.
123
