Maximum Inscribed and Minimum Enclosing Tropical Balls of Tropical Polytopes and Applications to Volume Estimation and Uniform Sampling

David Barnhill Ruriko Yoshida Keiji Miura

Abstract

We consider a minimum enclosing and maximum inscribed tropical balls for any given tropical polytope over the tropical projective torus in terms of the tropical metric with the max-plus algebra. We show that we can obtain such tropical balls via linear programming. Then we apply minimum enclosing and maximum inscribed tropical balls of any given tropical polytope to estimate the volume of and sample uniformly from the tropical polytope.

1 Introduction

Tropical polytopes [30, 23] are gaining popularity as a tropical counterpart of classical polytopes. It is expected that tropical convex geometry has potential to solve many problems [36, 39, 32, 37, 38], just as classical convex geometry has many applications. In fact, tropical polytopes over the tropical projective space have been studied thoroughly (for examples, see [30, 23, 35] and references within) and have been applied in many areas, such as statistics, optimization, and phylogenomics [30, 36, 39, 32, 35, 11].

In polyhedral geometry, the minimum enclosing ball (or sphere) of a given polytope is the smallest ball in terms of the Euclidean metric, $l_{2}$ -norm, containing the given polytope. The maximum inscribed ball of a polytope is the largest ball in terms of $l_{2}$ -norm that is contained in the polytope. Computing the minimum enclosing ball and maximum inscribed ball of a polytope is a challenging problem [26, 31]. The maximum inscribed ball of a given polytope is closely related to the interior point method for linear programming, and both the minimum enclosing ball and the maximum inscribed ball of a given polytope have been applied to solving linear programming problems [31], to computing support vector machines [7, 8], and to estimate the volume of polytopes [22].

In this paper, we consider tropical balls in terms of the tropical metric over the tropical projective torus with the max-plus algebra. A tropical ball $B_{l}(x_{0})$ , which is formally defined in Definition 3.2, with the radius $l>0$ at the center $x_{0}$ is defined as the set of all points over the tropical projective torus with the tropical metric $d_{\rm tr}$ defined in Definition 2.4 from $x_{0}$ less than or equal to $l$ . Put simply, a tropical ball is equivalent to a ball over an Euclidean space by replacing the $l_{2}$ -norm with the tropical metric $d_{\rm tr}$ . A tropical polytope over the tropical projective torus is the smallest tropically convex set of finitely many points from the tropical projective torus. This is an analogue of a classical polytope over an Euclidean space, which is the smallest convex set of finitely many points in the Euclidean space. Similar to a minimum enclosing ball and maximum inscribed ball of a classical polytope, a minimum enclosing tropical ball of a tropical polytope is the smallest tropical ball containing the tropical polytope and a maximum inscribed tropical ball of a tropical polytope is the largest tropical ball contained in the given tropical polytope. In this paper we show that the linear programming problem formulated in (5)-(9) below provides the center, $x_{0}$ , and the radius, $R>0$ , of the maximum inscribed tropical ball and the linear programming problem formulated in (14)-(16) below provides the center, $y_{0}$ , and the radius, $r>0$ , of the minimum enclosing tropical ball of a given tropical polytope in the tropical projective torus.

It is hard to compute the volume of a polytope. In general, a tropical polytope does not have to be classically convex in terms of the Euclidean metric and it can have some components which are of lower dimension than the tropical projective torus [23] as shown in Figure 1.

Refer to caption — Figure 1: Best-fit tropical triangle over the space of phylogenetic trees for the Apicomplexa genome data from Kuo et al. [27] computed by tropical principal component analysis proposed by Yoshida et al. [36]. Grey points on the tropical triangle are projected points via the tropical metric from observations in the data.

Therefore, computing the Euclidean volume of a tropical polytope over the tropical projective torus is #-P hard and even estimating the approximate volume of a tropical polytope is NP-hard in general [19]. In a Euclidean space, counting the number of lattice points in a classical polytope and computing the volume of the polytope are strongly related by Ehrhart theory [13], and are #-P hard problems even though an input polytope is described by an oracle [15]. As a specific case, Brandenburg et al. [5] apply tools from toric geometry to compute multivariate versions of volume, Ehrhart and $h^{*}$ -polynomials of lattice polytropes, which are tropically and classically convex sets of finitely many lattice points.

In Euclidean space, Cousins and Vempala [10] apply a minimum enclosing ball and Gaussian distributions to estimating the volume of a classical polytope via simulated annealing sampling. In this paper we develop a novel method to estimate the Euclidean volume of a tropical polytope over the tropical projective torus with the max-plus algebra using the minimum enclosing tropical ball of a tropical polytope, and a Hit-and-Run (HAR) sampler proposed by Yoshida, et al. [38]. We note that the ratio of the volume of a minimum enclosing tropical ball and the volume of a maximum inscribed tropical ball of a tropical polytope is an approximation of an acceptance rate of a sampler and in general this ratio can be very small. Therefore, it is still difficult to estimate the volume of a tropical polytope in general.

Sampling from a tropical polytope itself is an important issue. Yoshida et al. [38] propose a HAR sampler using the tropical line segment with the tropical metric to sample from a tropically convex set. They showed that their HAR sampler with the tropical metric can sample uniformly from a polytrope, so that using a decomposition of a tropical polytope into a set of tropical simplicies, which are polytropes, described in [24], one can sample uniformly from a tropical polytope. However, they have not described explicitly how to sample uniformly from a tropical polytope in general and they do not implement their proposed method explicitly. Thus, in this paper, we apply a minimum enclosing tropical ball of a tropical polytope combined with a HAR sampler using the tropical metric to sample uniformly from a tropical polytope in general.

This paper is organized as follows: Section 2 provides basics of tropical geometry. In section 3, we illustrate how to find the maximum inscribed and minimum enclosing tropical balls for a given tropical polytope. We remind readers how to construct the hyperplane, or $h^{*}-representation$ , of a tropical polytope with a given vertex set described in [5]. Using the $h^{*}-representation$ , we show how to compute the maximum inscribed tropical ball using linear programming. Next, we describe how we can, again, use linear programming to construct the minimum enclosing tropical ball. In section 4, we show how, by sampling from the minimum enclosing tropical ball using the HAR method described in [38] we can obtain a volume estimate of the tropical polytope, $P$ . In addition, we show that if $P\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}$ is defined by $e$ vertices, methods exist to identify the union of full-dimensional cells, or (e-1)-trunk (Definition 2.16), of a tropical polytope, reducing the radius of the minimum enclosing tropical ball and therefore the number of sample points necessary to obtain a volume estimate of $P$ . In section 5, we show that sampling from the minimum enclosing tropical ball and enumerating the tropical simplices defining the defining $P$ of the tropical polytope allows uniform sampling of the $(e-1)$ -trunk of any tropical polytope.

All computational experiments were conducted with R, statistical computational tool. The R code used for this paper is available at https://github.com/barnhilldave/Tropical-Balls.git.

2 Tropical Basics

Throughout this paper, we consider the tropical projective torus $\mathbb{R}^{e}\!/\mathbb{R}{\bf 1}$ , where
${\bf 1}:=(1,1,\ldots,1)\in R^{e}$ is the vector of all ones. This means that we have

(x_{1}+c,x_{2}+c,\ldots,x_{e}+c)=(x_{1},x_{2},\ldots,x_{e})

for any $c\in\mathbb{R}$ and for any vector $x:=(x_{1},x_{2},\ldots,x_{e})\in\mathbb{R}^{e}\!/\mathbb{R}{\bf 1}$ . For more details, see [30] and [23].

Definition 2.1 (Tropical Arithmetic Operations).

Under the tropical semiring with the max-plus algebra $(\,\mathbb{R}\cup\{-\infty\},\oplus,\odot)\,$ , we have the tropical arithmetic operations of addition and multiplication defined as:

x\oplus y:=\max\{x,y\},~{}~{}~{}~{}x\odot y:=x+y~{}~{}~{}~{}\mbox{ where }x,y\in\mathbb{R}\cup\{-\infty\}.

Note that $-\infty$ is the identity element under addition $\oplus$ and $0$ is the identity element under multiplication $\odot$ over this semiring.

On the other hand, under the tropical semiring with the min-plus algebra $(\,\mathbb{R}\cup\{\infty\},\boxplus,\odot)\,$ , we have the tropical arithmetic operations of addition and multiplication defined as:

x\boxplus y:=\min\{x,y\},~{}~{}~{}~{}x\odot y:=x+y~{}~{}~{}~{}\mbox{ where }x,y\in\mathbb{R}\cup\{\infty\}.

Definition 2.2 (Tropical Scalar Multiplication and Vector Addition).

For any $x,y\in\mathbb{R}\,\cup\,\{-\infty\}$ and for any $v=(v_{1},\ldots,v_{e}),\;w=(w_{1},\ldots,w_{e})\in(\mathbb{R}\cup\{-\infty\})^{e}$ , we have tropical scalar multiplication and tropical vector addition defined as:

x\odot v\oplus y\odot w:=(\max\{x+v_{1},y+w_{1}\},\ldots,\max\{x+v_{e},y+w_{e}\}).

Definition 2.3 (Tropical Matrix Operations).

Suppose we have two $(k_{1}\times k_{2})$ -dimensional matrices $A,B$ and an $(k_{3}\times k_{1})$ -dimensional matrix $C$ with entries in $\mathbb{R}\cup\{-\infty\}$ . Then we can define the tropical matrix operations $A\oplus B$ and $A\otimes C$ in analogy with the ordinary matrix operations. Specifically, we have

(A\oplus B)_{ij}=A_{ij}\oplus B_{ij},\ \ (A\otimes C)_{ij}=\bigoplus_{\ell=1}^{k_{1}}A_{i\ell}\otimes C_{\ell j}.

Definition 2.4 (Generalized Hilbert Projective Metric).

For any points $v:=(v_{1},\ldots,v_{e}),\,w:=(w_{1},\ldots,w_{e})\in\mathbb{R}^{e}\!/\mathbb{R}{\bf 1}$ where $[e]:=\{1,\ldots,e\}$ , the tropical distance (also known as tropical metric) $d_{\rm tr}$ between $v$ and $w$ is defined as:

d_{\rm tr}(v,w):=\max_{i\in[e]}\bigl{\{}v_{i}-w_{i}\bigr{\}}-\min_{i\in[e]}\bigl{\{}v_{i}-w_{i}\bigr{\}}.

Definition 2.5 (Tropical Polytopes).

Suppose we have $S\subset\mathbb{R}^{e}\!/\mathbb{R}{\bf 1}$ . If

x\odot v\oplus y\odot w\in S

for any $x,y\in\mathbb{R}$ and for any $v,w\in S$ , then $S$ is called tropically convex. Suppose $V=\{v^{1},\ldots,v^{s}\}\subset\mathbb{R}^{e}\!/\mathbb{R}{\bf 1}$ . The smallest tropically convex subset containing $V$ is called the tropical convex hull or tropical polytope of $V$ which can be written as the set of all tropical linear combinations of $V$

\mathrm{tconv}(V)=\{a_{1}\odot v^{1}\oplus a_{2}\odot v^{2}\oplus\cdots\oplus a_{s}\odot v^{s}\mid a_{1},\ldots,a_{s}\in\mathbb{R}\}.

The smallest subset $V^{\prime}\subseteq V$ such that

\mathrm{tconv}(V^{\prime})=\mathrm{tconv}(V)

is called a minimum set or a generating set with $|V^{\prime}|$ being the cardinality of $V^{\prime}$ . For $P=\text{tconv\,}(V^{\prime})$ the boundary of $P$ is denoted $\partial P$ .

We call a max-tropical polytope if a tropical polytope is defined in terms of the max-plus algebra and we call a min-tropical polytope if a tropical polytope is defined in terms of the min-plus algebra.

Definition 2.6 (Polytropes (See [24])).

A classically convex tropical polytope is called a polytrope.

Definition 2.7 (Covector Decomposition (From [11] and [29])).

A tropical polytope may be decomposed into a polyhedral complex of polytropes known as a covector decomposition of $P$ , denoted as $\mathcal{C}_{P}$ .

Definition 2.8 (Dimension of a Tropical Polytope).

The dimension of a tropical polytope, $P\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}$ , is defined by the polytrope of maximal dimension in $\mathcal{C}_{P}$ and is denoted as $dim(P)$ .

Next we remind the reader of the definition of a projection in terms of the tropical metric onto a tropical polytope. The tropical projection formula can be found as Formula 5.2.3 in [30].

Definition 2.9 (Projections of Tropical Points).

Let $V:=\{v^{1},\ldots,v^{s}\}\subset\mathbb{R}^{e}/{\mathbb{R}}{\bf 1}$ and let $P=\text{tconv\,}(v^{1},\ldots,v^{s})\subseteq\mathbb{R}^{e}/\mathbb{R}{\bf 1}$ be a tropical polytope with its vertex set $V$ . For $x\in\mathbb{R}^{e}\!/\mathbb{R}{\bf 1}$ , let

\pi_{P}(x)\!:=\!\bigoplus\limits_{l=1}^{s}\lambda_{l}\odot v^{l},~{}~{}{\rm where}~{}~{}\lambda_{l}\!=\!{\rm min}(x-v^{l}).

(1)

Then

d_{\rm tr}(x,\pi_{P}(x))\leq d_{\rm tr}(x,y)

for all $y\in P$ and $\pi_{P}(x)\in P$ . In other words, $\pi_{P}(x)$ is the projection of $x\in\mathbb{R}^{e}\!/\mathbb{R}{\bf 1}$ in terms of the tropical metric $d_{\rm tr}$ onto the tropical polytope $P$ .

The following definitions describe the relationship between tropical hyperplanes and tropical polytopes. Specifically, they illustrate the connection between max-tropical polytopes and min-tropical hyperplanes.

Definition 2.10 (Tropical Hyperplane from [39]).

For any $\omega:=(\omega_{1},\ldots,\omega_{e})\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}$ , the max-tropical hyperplane defined by $\omega$ , denoted as $H_{\omega}^{\max}$ , is the set of points $x\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}$ such that

\max_{i\in[e]}\Big{\{}\omega_{i}+x_{i}\Big{\}}

(2)

is attained at least twice. Similarly, a min-tropical hyperplane denoted as $H^{\min}_{\omega}$ , is the set of points $x\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}$ such that

\min_{i\in[e]}\Big{\{}\omega_{i}+x_{i}\Big{\}}

(3)

is attained twice. If it is clear from a content, we simply denote $H_{\omega}$ as a tropical hyperplane in terms of the min-plus or max-plus algebra where $\omega$ is the normal vector of $H_{\omega}$ .

Definition 2.11 (Sectors from [39]).

Every tropical hyperplane, $H_{\omega}$ , divides the tropical projective torus, $\mathbb{R}^{e}/\mathbb{R}\mathbf{1}$ into $e$ connected components, which are open sectors

S^{i}_{\omega}:=\{x\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}\,|\,\omega_{i}+x_{i}>\omega_{j}+x_{j},\forall j\neq i\},\;i=1,\ldots,e.

These closed sectors are defined as

\overline{S}^{i}_{\omega}:=\{x\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}\,|\,\omega_{i}+x_{i}\geq\omega_{j}+x_{j},\forall j\neq i\},\;i=1,\ldots,e.

Definition 2.12 (Tropical Hyperplane Arrangements).

For a given set of points, $V=\{v^{1},\ldots,v^{s}\}$ , tropical hyperplanes with apices at each $v^{i}\in V$ represent the tropical hyperplane arrangement of $V$ , $\mathcal{A}(V)$ , where

\mathcal{A}(V):=\{H_{-v^{1}},\ldots,H_{-v^{s}}\}.

If we consider a collection of tropical hyperplanes defined in terms of the max-plus algebra, we call this arrangement a max-tropical hyperplane arrangement denoted $\mathcal{A}^{\max}(V)$ . Likewise, considering tropical hyperplanes defined in terms of the min-plus algebra is called a min-tropical hyperplane arrangement denoted $\mathcal{A}^{\min}(V)$ .

Definition 2.13 (Cells).

For a given hyperplane arrangement, $\mathcal{A}(V)$ , a cell is defined as the intersection of a finite number of closed sectors. Cells may be bounded or unbounded. Bounded cells are polytropes.

Definition 2.14 (Bounded Subcomplex (See [11])).

For a vertex set, $V$ , $\mathcal{A}(V)$ defines a collection of bounded and unbounded cells which is known as a cell decomposition. The union of bounded cells defines the bounded subcomplex, $\mathcal{K}(V)$ .

Theorem 2.15 (Theorem 2.2 in [12]).

A $\max$ -tropical polytope, $P$ , is the union of cells in $\mathcal{K}(V)$ of the cell decomposition of the tropical projective torus induced by $\mathcal{A}^{\min}(V)$ .

Theorem 2.15 describes a $\mathcal{K}(V)$ as a collection of bounded cells induced by $\mathcal{A}(V)$ . Definition 2.7 describes $P$ in terms of a union of polytropes. The bounded cells induced by $\mathcal{A}^{\min}(V)$ are these polytropes. Therefore, the union of the polytropes in $\mathcal{C}_{P}$ defines $\mathcal{K}(V)$ . Throughout this paper we are interested in sampling the union of $(e-1)$ -dimensional polytropes belonging to $\mathcal{K}(V)$ . The union of $(e-1)$ -dimensional polytropes is described in the following definition.

Definition 2.16 (i-trunk and i-tentacles (Definition 2.1 in [29])).

Let $P$ be a tropical polytope and let $i\in[e-1]$ where $[e-1]=\{1,\ldots,e-1\}$ . Let $\mathcal{F}_{P}$ be the family of relatively open tropical polytopes in $\mathcal{C}_{P}$ . For any $T\in\mathcal{F}_{P}$ , $T$ is called an i-tentacle element of $\mathcal{F}_{P}$ if it is not contained in the closure of any $(i+1)$ -dimensional tropical polytope in $\mathcal{F}_{P}$ where the dimension of $T$ less than or equal to $i$ . The i-trunk of $P$ , is defined as

Tr_{i}(P):=\bigcup\Big{\{}F\in\mathcal{F}_{P}:\exists\;G\in\mathcal{F}_{P}\text{ with }\dim(G)\geq i\text{ such that }F\subseteq G\Big{\}}

where $dim(G)$ is the dimension of $G\subset\mathcal{F}_{P}$ . The $Tr_{i}(P)$ represents the portion of the $\mathcal{K}(V)$ with $(i-1)$ -tentacles removed. The minimum enclosing ball containing containing only $Tr_{i}(P)\subseteq P$ is denoted $B_{k}(Tr_{i}(P))$ .

Remark 2.17 (Proposition 2.3 in [5]).

The $Tr_{e-1}(P)$ of a tropical polytope, $P\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}$ is a tropical polytope.

Example 2.18.

Consider the tropical polytope, $P=\{(0,0,0),(0,-1,1),(0,2,2),(0,1,-1)\}$ . The $Tr_{2}(P)$ is the gray portion shown in Figure 2.

Figure 2: A tropical polytope,

P

, in

\mathbb{R}^{3}/\mathbb{R}\mathbf{1}

defined by four vertices. The

Tr_{2}(P)

is the portion in gray.

All methods described in this paper involve sampling from the $Tr_{e-1}(P)$ of a tropical polytope $P$ . However, tropical polytopes can exist without a $Tr_{e-1}(P)$ as shown by Joswig et al. (See Figure 1 (left) in [24]). Therefore, all tropical polytopes considered in this research are assumed to contain a $Tr_{e-1}(P)$ .

3 Using Optimization to Find Maximum Inscribed and Minimum Enclosing Tropical Balls

In this section we illustrate how to find the hyperplane-representation of a tropical simplex $P_{\Delta}$ , in order to compute the maximum incscribed ball of $P_{\Delta}$ . We then show how to calculate the minimum enclosing ball of any tropical polytope $P$ , using a linear programming formulation. Tropical simplices and tropical balls will be leveraged throughout this paper thus we offer the following definitions.

Definition 3.1 (Tropical Simplex).

A tropical simplex is a tropical polytope that possess a minimum vertex, or generating, set $V^{\prime}$ such that $|V^{\prime}|=e$ . A tropical simplex is denoted $P_{\Delta}$ .

Definition 3.2 (Tropical Ball).

A tropical ball, $B_{l}(x_{0})$ , around $x_{0}\in\mathbb{R}^{e}/\mathbb{R}{\bf 1}$ with a radius $l>0$ is defined as follows:

B_{l}(x_{0})=\{y\in\mathbb{R}^{e}/\mathbb{R}{\bf 1}\,|\,d_{\rm tr}(x_{0},y)\leq l\}.

For a tropical polytope, $P$ , the minimum enclosing ball, denoted as $B_{r}(P)$ , is the tropical ball of smallest radius $r$ that fully contains $P$ . For the same $P$ , the tropical ball with maximum radius $R$ , that is fully contained in $P$ is called the maximum inscribed ball and is denoted $B_{R}(P)$ .

3.1 Hyperplane Representation of Tropical Polytopes with the Max-Plus Algebra

Brandenburg et al. in [5] show that the hyperplane-representation of a polytrope $P$ , denoted as $h^{*}-representation(P)$ , can be constructed from an associated Kleene Star weight matrix, $\mathbf{m^{*}}$ . This is shown in the following definition and extends it to any $P_{\Delta}$ .

Definition 3.3 (Hyperplane Representation of a Tropical Simplex (See Proposition 2.14 in [5])).

For a tropical simplex that is a polytrope, $P_{\Delta}\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}$ , $P_{\Delta}$ may be defined by the intersection of a collection of classical half-spaces. These half-spaces are constructed using a Kleene Star weight matrix, $\mathbf{m^{*}}$ , where each $m_{ij}$ is the $(i,j)$ -th entry in $\mathbf{m^{*}}$ . The half-spaces defining $P_{\Delta}$ are constructed as follows

P_{\Delta}=\{y\in\mathbb{R}^{e}\;|\;y_{j}-y_{i}\leq-m_{ij},y_{1}=0,m_{ij}\in\mathbf{m^{*}},i\neq j\}.

(4)

We denote this intersection of half-spaces as $h^{*}-representation(P_{\Delta})$ . By contrast, the vertex representation of $P_{\Delta}$ using a vertex set, $V$ , is denoted as $v-representation(P_{\Delta})$ . For a tropical simplex, $P_{\Delta}$ , that is not classically convex, the $h^{*}-representation(P_{\Delta})$ only defines the $(e-1)$ -trunk of $P$ (See Definition 2.16).

For any weight matrix $\mathbf{m}\in\mathbb{R}^{e\times e}$ associated with a complete graph of $e$ nodes with no positive cycles, $m_{ij}$ represents the weight from node $i$ to $j$ with the diagonal being all zeroes. The weight matrix, $\mathbf{m^{*}}$ , can be constructed by taking the $(e-1)$ -th tropical power of $\mathbf{m}$ . that is, $\textbf{m}^{\odot e-1}$ with each $m_{ij}\in\mathbf{m^{*}}$ being the maximal path from node $i$ to node $j$ [4, 34]. From the new matrix $\mathbf{m^{*}}$ , we can obtain $h^{*}-representation(P)$ using (4) [5].

In this paper we start with a vertex set, $V^{\prime}$ , defining a tropical simplex, $P_{\Delta}=\text{tconv\,}(V^{\prime})$ and where we assume that $V^{\prime}$ is a minimum vertex set. Using $V^{\prime}$ we then construct $\mathbf{m^{*}}$ . By Proposition 2.14 in [5], there is a correspondence between the $\mathbf{m^{*}}$ and the points in $V^{\prime}$ .

To build $\mathbf{m^{*}}$ , we must first calculate the tropical determinant of a matrix $A$ , using Definition 3.4, where column vectors, $A_{j}$ , are tropical points $V^{\prime}$ .

Definition 3.4 (Tropical Determinant).

Let $q$ be a positive integer. For any squared tropical matrix $A$ of size $q\times q$ with entries in $\mathbb{R}\;\cup\;\{-\infty\}$ , the tropical determinant of $A$ is defined as:

tdet(A):=\max_{\sigma\in S_{q}}\{A_{\sigma(1),1}+A_{\sigma(2),2}+\ldots+A_{\sigma(q),q}\},

where $S_{q}$ is all the permutations of $[q]:=\{1,\ldots,q\}$ , and $A_{i,j}$ denotes the $(i,j)$ -th entry of A. The tropical matrix is singular if:

1.

A is non-square;
2.

the $tdet(A)=-\infty$ ; or
3.

at least two permutations achieve the maximum $tdet(A)$ .

For a square matrix, it is equivalent to saying the row or column vectors lie in a tropical hyperplane (see Proposition 3.4 in [23]).

Finding $tdet(A)$ can be reduced to evaluating a linear assignment problem where $e$ tasks are assigned to $e$ workers to achieve maximum benefit. Each $i,j\in[e]$ , the $(i,j)$ th element of the matrix $A$ , $A_{i,j}$ , represents the benefit gained from assigning task $i$ to worker $j$ . The $tdet(A)$ provides the permutation that achieves this maximum benefit (See Observation 3.1 in [23]).

After calculating $tdet(A)$ , let $\sigma_{P}$ be the permutation satisfying $tdet(A)$ as shown in Definition 3.4. The output of Algorithm 1 is an $e\times e$ tropical matrix $A^{\prime}$ whose diagonal is $A_{\sigma_{P}(i),i}$ .

Algorithm 1 Calculating the

tdet(A)

and

\sigma_{P}\in S_{e}

for a square matrix,

A

Input: A square matrix,

A

, with the column vectors representing the set of vertices in

V^{\prime}

Output:

tdet(A)

and

\sigma_{P}\in S_{e}

Enumerate each permuation,

\sigma_{k}

, of the row indices of

A

where

\sigma_{k}\in S_{e}

Calculate

t(\sigma_{k})=\sum\limits_{i=1}^{e}A_{\sigma_{k}(i),i}

for each

\sigma_{k}\in S_{e}

Let

tdet(A)=

\max\limits_{k}\,

(t(\sigma_{k}))

and

\sigma_{P}=\sigma_{k}

return

tdet(A)

and

\sigma_{P}

Example 3.5.

Consider the polytrope, $P_{\Delta}:=\text{tconv\,}(\{(0,0,0),(0,2,5),(0,3,1)\})$ . Letting the vertices be the column vectors of a square matrix $A$ , we find $tdet(A)=8$ with $\sigma_{P}=(1,3,2)$ where the index of $\sigma_{P}$ represents the column and the value at that index represents the row index of that column. This tells us that coordinates of the matrix, $A$ , contributing to $tdet(A)$ are $A_{1,1}=0$ , $A_{3,2}=5$ , and $A_{2,3}=3$ . Reordering the columns from smallest row index to largest yields the new matrix, $A^{\prime}$ , as follows,

A=\left(\begin{array}[]{ccc}0&0&0\\ 0&2&3\\ 0&5&1\end{array}\right)\rightarrow\left(\begin{array}[]{ccc}0&0&0\\ 0&3&2\\ 0&1&5\end{array}\right)=A^{\prime}.

The final step to find $\mathbf{m^{*}}$ is to add $-A^{\prime}_{kk}\in A^{\prime}$ to each element of the column, $A^{\prime}_{k}$ for $k\in[e]$ . The result of this operations finalizes the construction of $\mathbf{m^{*}}$ . Once $\mathbf{m^{*}}$ is constructed, we can extract $h^{*}-representation(P_{\Delta})$ using (4). To illustrate extracting $h^{*}-representation(P_{\Delta})$ , we use Algorithm 2.

Algorithm 2 Extracting

h^{*}-representation(P_{\Delta})

of a tropical simplex

P\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}

Input: A square matrix,

A

, representing a set of vertices in minimum vertex set

V^{\prime}

where the vertices are the columns of

A

Output:

h^{*}-representation(P_{\Delta})

Calculate

tdet(A)

and identify

\sigma_{P}\in S_{e}

defining

tdet(A)

using Algorithm 1.

Reorder the columns to form a new matrix

A^{\prime}

such that

A_{\sigma_{P}(i),i}=A^{\prime}_{kk}

where

k=\sigma_{P}(i)

For a matrix,

\mathbf{m^{*}}\in\mathbb{R}^{e\times e}

, let

m_{jk}=A^{\prime}_{jk}-A^{\prime}_{kk}

for all

j,k\in[e]

Compute

h^{*}-representation(P_{\Delta})

from,

\mathbf{m^{*}}

, using (4).

return

h^{*}-representation(P_{\Delta})

Example 3.6 (Example 3.5 cont’d).

Continuing with the polytrope, $P_{\Delta}$ , from the previous example we move to the next step to construct the $h^{*}-representation(P_{\Delta})$ . After finding the $tdet(A)$ and reordering the columns to form the new matrix, $A^{\prime}$ , $-A^{\prime}_{kk}$ is added to each element of the column vector $A^{\prime}_{k}$ to construct $\mathbf{m^{*}}$ . The result follows,

\left(\begin{array}[]{ccc}0&-3&-5\\ 0&0&-3\\ 0&-2&0\end{array}\right)=\mathbf{m^{*}}.

The $h^{*}-representation(P_{\Delta})$ , as described in (4), is shown below

	$\displaystyle y_{2}-y_{1}\leq$	$\displaystyle 3$
	$\displaystyle y_{3}-y_{1}\leq$	$\displaystyle 5$
	$\displaystyle y_{1}-y_{2}\leq$	$\displaystyle 0$
	$\displaystyle y_{3}-y_{2}\leq$	$\displaystyle 3$
	$\displaystyle y_{1}-y_{3}\leq$	$\displaystyle 0$
	$\displaystyle y_{2}-y_{3}\leq$	$\displaystyle 2$
	$\displaystyle y_{1}=$	$\displaystyle\;0.$

Figure 3 shows the directed graph and polytrope defined by $\mathbf{m^{*}}$ . The directed graph represents the maximum distance between any two nodes as determined by $\mathbf{m^{*}}$ .

While [5] specifically addresses $h^{*}-representation(P_{\Delta})$ for polytropes, this method can also be used for any tropical simplex. However, the $h^{*}-representation(P_{\Delta})$ only defines the $Tr_{e-1}(P_{\Delta})$ , resulting in several redundant constraints.

Figure 3: Directed graph determined by the Kleene Star for Example 3.6.

3.1.1 Maximum Inscribed Balls for Tropical Polytopes

We now illustrate how to use (4) to formulate a linear program to construct the maximum inscribed ball for a tropical simplex $P_{\Delta}$ denoted as $B_{R}(P_{\Delta})$ . Like any polytrope, a tropical ball, $B_{l}(x_{0})\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}$ can be defined as a tropical simplex with a minimum vertex set $V^{\prime}$ such that $B_{l}(x_{0})=\text{tconv\,}(V^{\prime})$ .

Given a point, $x_{0}:=(x_{0}^{1},\ldots,x_{0}^{e})$ , representing the center of a $B_{l}(x_{0})$ , we can obtain vertices in $V^{\prime}$ for $B_{l}(x_{0})$ such that $B_{l}(x_{0})=\text{tconv\,}(V^{\prime})$ where

V^{\prime}=\left\{\begin{array}[]{ccc}(x_{0}^{1}-l,x_{0}^{2}-l,x_{0}^{3}-l\ldots,x_{0}^{e}-l),\\ (x_{0}^{1}+l,x_{0}^{2},x_{0}^{3},\ldots,x_{0}^{e}),\\ \vdots\\ (x_{0}^{1},x_{0}^{2},x_{0}^{3},\ldots,x_{0}^{e}+l)\end{array}\right\}.

Example 3.7.

Let $x_{0}\in\mathbb{R}^{3}/\mathbb{R}\mathbf{1}$ represent the center of a tropical ball, $B_{l}(x_{0})$ with radius, $l$ where $x_{0}:=(0,x_{0}^{1},x_{0}^{2})$ . Because $B_{l}(x_{0})$ is a polytrope, the minimum vertex set, $V^{\prime}$ , consists of three vertices, where $B_{l}(x_{0})=\text{tconv\,}(V^{\prime})$ . Each $v^{i}\in V^{\prime}$ where $i\in[3]$ , can be represented in terms of $x_{0}$ and $l$ . Specifically,

	$\displaystyle v^{1}$	$\displaystyle=(0,x_{0}^{1}-l,x_{0}^{2}-l)$
	$\displaystyle v^{2}$	$\displaystyle=(0,x_{0}^{1},x_{0}^{2}+l)$
	$\displaystyle v^{3}$	$\displaystyle=(0,x_{0}^{1}+l,x_{0}^{2})$

Figure 4 illustrates the coordinate construction of $B_{l}(x_{0})\in\mathbb{R}^{3}/\mathbb{R}\mathbf{1}$ .

Figure 4: Tropical ball,

B_{l}(x_{0})\in\mathbb{R}^{3}/\mathbb{R}\mathbf{1}

with radius

l

Using the vertices in $V^{\prime}$ , we can compute $B_{R}(P_{\Delta})$ . To determine if $B_{l}(x_{0})$ falls inside $P_{\Delta}$ , it suffices to check if the vertices in $V^{\prime}$ defining $B_{l}(x_{0})$ are in the $P_{\Delta}$ . Therefore, to find $B_{R}(P_{\Delta})$ , we check that each vertex defining $B_{R}(P_{\Delta})$ is inside of the tropical polytope $P_{\Delta}$ with the center point, $x_{0}$ and the maximum radius, $R$ . The linear program shown in (5)-(9) finds $B_{R}(P_{\Delta})$ by constructing the $h^{*}-representation(B_{R}(P_{\Delta}))$ in terms of its center, $x_{0}$ , as shown in Figure 4.

$\displaystyle\text{$\max_{R,x_{0}}$}\quad R$		(5)
$\displaystyle\;\text{s.t.}\quad\;(x_{0}^{i}+R)-x_{1}\leq-m_{1i}$	$\displaystyle\quad\forall\;i\in\{2,\dots,e\}$	(6)
$\displaystyle\;x_{1}-(x_{0}^{j}-R)\leq-m_{j1}$	$\displaystyle\quad\forall\;j\in\{2,\ldots,e\}$	(7)
$\displaystyle\;(x_{0}^{j}+R)-x_{0}^{i}\leq-m_{ij}$	$\displaystyle\quad\forall\;i,j\in\{2,\ldots,e\},\;i\neq j$	(8)
$\displaystyle\;x_{0}^{1}=0.$		(9)

To check if a vertex is inside $P_{\Delta}$ , we leverage (4). Because the first coordinate is special (i.e., $x_{1}=0$ ), we separately consider the constraint in (4) for $j=1$ , $i=1$ or the other cases. Note that inequalities are mostly redundant for the vertices in $V^{\prime}$ defining $B_{R}(P_{\Delta})$ . Therefore only the non-redundant inequality is kept finally in the formulation above.

Notably, the $B_{R}(P_{\Delta})$ need not to be unique. Results from the following example show that $B_{R}(P_{\Delta})$ can have a center point, $x_{0}$ , from $(0,1.5,1.5)$ to $(0,1.5,3)$ and achieve the desired result.

Example 3.8.

We again consider the tropical simplex, $P_{\Delta}$ , defined in Example 3.6. The formulation to find $B_{R}(P_{\Delta})$ is

	$\displaystyle\text{$\max_{R,x_{0}}$}\quad R$
	$\displaystyle\;\text{s.t.}\quad\;x_{0}^{1}-(x_{0}^{2}-R)\leq 0$
	$\displaystyle\;x_{0}^{1}-(x_{0}^{3}-R)\leq 0$
	$\displaystyle\;(x_{0}^{2}+R)-x_{0}^{1}\leq 3$
	$\displaystyle\;(x_{0}^{3}+R)-x_{0}^{1}\leq 5$
	$\displaystyle\;(x_{0}^{3}+R)-x_{2}\leq 3$
	$\displaystyle\;(x_{0}^{2}+R)-x_{0}^{3}\leq 2$
	$\displaystyle\;x_{0}^{1}=0.$

This results in $x_{0}=(0,1.5,1.5)$ and radius, $R=1.5$ . Figure 5 shows $B_{R}(P)$ .

3.1.2 Maximum Inscribed Balls for General Tropical Polytopes

In the previous section, we focus on computing maximum inscribed balls for tropical simplices. In this section, we show that we can apply the same process and formulation shown in (5)- (9) to any tropical polytopes $P$ to find $B_{R}(P)$ . To do this we focus on the set of tropical simplices in the tropical simplicial complex of $P$ , $\Delta_{P}$ , determined by the $t=\binom{n}{e}$ combinations of vertices in the minimum vertex set of $P$ , $V^{\prime}$ with $|V^{\prime}|=n$ [17].

Definition 3.9 (Tropical Simplicial Complex (See [17])).

Let $V$ be a set of points such that $\text{tconv\,}(V)=P\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}$ , the collection of tropical polytopes defined by all subsets $V^{\prime}\subseteq V$ where $|V^{\prime}|\leq e$ and a tropical polytope $P^{\prime}=\text{tconv\,}(V^{\prime})$ , is known as the tropical simplicial complex, denoted as $\Delta_{P}$ . We say $\Delta_{P}$ is pure if all facets in $\Delta_{P}$ has the same cardinality.

Only tropical polytopes of $e$ or more vertices may contain a $Tr_{(e-1)}(P)$ . Therefore we apply (5)-(9) to each tropical simplex in $\Delta_{P}$ , denoted $P_{\Delta}^{i}\in\Delta_{P}$ , to construct $B_{R_{i}}(P_{\Delta}^{i})$ where $R_{i}$ is the radius of the maximum inscribed ball for $P_{\Delta}^{i}$ . Since $\bigcup_{i=1}^{t}P_{\Delta}^{i}=P$ , we have $\bigcup_{i=1}^{t}Tr_{e-1}(P_{\Delta}^{i})=Tr_{e-1}(P)$ . Therefore, $B_{R}(P)=B_{R_{i}}(P_{i})$ for the $P_{i}\in\Delta_{P}$ where $R_{i}$ is the largest.

Example 3.10 (Borrowed from [29]).

Consider a tropical polytope $P:=\text{tconv\,}(\{(0,-2,5),(0,-2,3),$
$(0,2,2),(0,1,0)\})$ . Figure 6 illustrates this tropical polytope.

There are four tropical simplices in $\Delta_{P}$ , so to compute $B_{R}(P)$ we must apply (5)-(9) to evaluate each one. Figure 7 shows the four tropical simplices.

In Figure 7, the bottom two tropical simplices will yield the $B_{R}(P)$ . For brevity we show the $h*-representation(P)$ for the bottom right tropical simplex and linear program formulation using (5)-(9).

	$\displaystyle\text{$\max_{R,x_{0}}$}\quad R$
	$\displaystyle\;\text{s.t.}\quad\;x_{0}^{1}-(x_{0}^{2}-R)\leq 2$
	$\displaystyle\;x_{0}^{1}-(x_{0}^{3}-R)\leq-3$
	$\displaystyle\;(x_{0}^{2}+R)-x_{0}^{1}\leq 1$
	$\displaystyle\;(x_{0}^{3}+R)-x_{0}^{1}\leq 5$
	$\displaystyle\;(x_{0}^{3}+R)-x_{0}^{2}\leq 7$
	$\displaystyle\;(x_{2}+R)-x_{0}^{3}\leq 1$
	$\displaystyle\;x_{0}^{1}=0.$

The $B_{R}(P)$ center point and radius are $x_{0}=(0,-1,4)$ and $R=1$ , respectively.

This final example illustrates the use of the formulation in (5)-(9) of a tropical simplex which is not a polytrope.

Example 3.11.

Consider a tropical simplex $P_{\Delta}=\{(0,0,0,0),(0,1,3,1),(0,1,2,5),(0,2,5,10)\}$ . Let $A$ be a matrix representing the points as column vectors. We calculate $tdet(A)=14$ , and order the columns such that $A_{\sigma(i),i}=a^{\prime}_{kk}$ where $\sigma(i)=k$ .

A=\left(\begin{array}[]{cccc}0&0&0&0\\ 0&1&1&2\\ 0&3&2&5\\ 0&1&5&10\end{array}\right)\rightarrow\left(\begin{array}[]{cccc}0&0&0&0\\ 0&1&1&2\\ 0&2&3&5\\ 0&5&1&10\end{array}\right)=A^{\prime}.

After constructing $A^{\prime}$ we add $-A^{\prime}_{kk}$ to each element of each column $A_{k}$ .

A^{\prime}=\left(\begin{array}[]{cccc}0&0&0&0\\ 0&1&1&2\\ 0&2&3&5\\ 0&5&1&10\end{array}\right)\rightarrow\left(\begin{array}[]{cccc}0&-1&-3&-10\\ 0&0&-2&-8\\ 0&1&0&-5\\ 0&4&-2&0\end{array}\right)=\mathbf{m^{*}}.

This results in the following program:

	$\displaystyle\text{$\max_{R,x_{0}}$}\quad R$
	$\displaystyle\;\text{s.t.}\quad\;x_{0}^{1}-(x_{0}^{2}-R)\leq 0$
	$\displaystyle\;x_{0}^{1}-(x_{0}^{3}-R)\leq 0$
	$\displaystyle\;x_{0}^{1}-(x_{0}^{4}-R)\leq 0$
	$\displaystyle\;(x_{0}^{2}+R)-x_{0}^{1}\leq 1$
	$\displaystyle\;(x_{0}^{3}+R)-x_{0}^{1}\leq 3$
	$\displaystyle\;(x_{0}^{4}+R)-x_{0}^{1}\leq 10$
	$\displaystyle\;(x_{0}^{3}+R)-x_{0}^{2}\leq 2$
	$\displaystyle\;(x_{0}^{4}+R)-x_{0}^{2}\leq 8$
	$\displaystyle\;(x_{0}^{2}+R)-x_{0}^{3}\leq-1$
	$\displaystyle\;(x_{0}^{4}+R)-x_{0}^{3}\leq 5$
	$\displaystyle\;(x_{0}^{2}+R)-x_{0}^{4}\leq-4$
	$\displaystyle\;(x_{0}^{3}+R)-x_{0}^{4}\leq 2$
	$\displaystyle\;x_{0}^{1}=0.$

Solving the above linear program results in a center point, $x_{0}=(0,.5,2,.5)$ with the radius, $R=0.5$ . Figure 9 shows $P_{\Delta}$ and $B_{R}(P_{\Delta})$ .

3.2 Minimum Enclosing Tropical Balls

Next we illustrate how we can formulate a linear programming problem to find the minimum enclosing ball, $B_{r}(P)$ , for a tropical polytope $P$ . We seek $y_{0}\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}$ to be the center point of $B_{r}(P)$ which minimizes $d_{tr}(y_{0},v_{i})$ for each $v_{i}\in V$ where $P=\text{tconv\,}(V)$ , such that $P\subset B_{r}(P)$ . The largest minimized $d_{tr}(y_{0},v_{i})$ for all $v_{i}\in V$ is the radius, $r$ , of $B_{r}(P)$ . Comăneci et al. showed in [9], that for any two points, $x,y\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}$ , $d_{tr}(x,y)$ can be rewritten in the following way:

d_{tr}(x,y)=\text{$\max_{i}$}(x-y)-\text{$\min_{j}$}(x-y)=\text{$\max_{\begin{subarray}{c}i,j\\ i\neq j\end{subarray}}$}(x_{i}-y_{i}-x_{j}+y_{j}).

(10)

We note that this is equivalent to the following formulation shown in [23],

d_{tr}(x,y)=\text{$\max_{1\leq i<j\leq e}$}(|x_{i}-y_{i}-x_{j}+y_{j}|).

(11)

Using the result from (10), we can formulate the following optimization problem for a given $V$ to find $y_{0}$ and $r$ of $B_{r}(P)$ .

	$\min_{y_{0}}$	$\displaystyle\text{$\max_{\begin{subarray}{c}i\in[\|V\|]\\ j,k\in[e]\\ j\neq k\end{subarray}}\,$}\left(v_{ij}-y_{0}^{j}-v_{ik}+y_{0}^{k}\right)$		(12)
		$\displaystyle\text{s.t. }v_{i}\in V.$		(13)

Because we are minimizing a maximum of a set of linear functions, the objective function in (12) may be further manipulated to formulate a linear program to solve for $y_{0}$ by replacing the maximum function with the variable $r$ , representing the radius of $B_{r}(P)$ . This formulation is shown in (14)-(16) as

$\displaystyle\text{$\min_{r,y_{0}}$}\quad r$		(14)
s.t.	$\displaystyle v_{i,j}-y_{0}^{j}-v_{i,k}+y_{0}^{k}\leq r\quad$	(15)
	$\displaystyle\indent\forall\;i\in[\|V\|];\,j,k\in\;[e],\;j\neq k,$
	$\displaystyle r\geq 0.$	(16)

Importantly, $y_{0}$ need not be in $P$ to construct $B_{r}(P)$ . Because (10) is equivalent to (11), either will result in the similar constraint construction (See Proposition 25 in [28]). To give a lower bound on the radius of $B_{r}(P)$ , we arrive at the following proposition.

Proposition 3.12.

For a minimum enclosing tropical ball of a tropical polytope $P$ , $B_{r}(P)$ with the radius $r$ satisfies the following inequality:

r\geq\max\limits_{i,j}\frac{d_{tr}(v_{i},v_{j})}{2},

(17)

where $v_{i},v_{j}\in V$ with $V$ being the vertex set of $P$ .

Proof.

Let $V^{\prime}$ be a minimum vertex set for a tropical polytope $P$ , where $P=\text{tconv\,}(V^{\prime})$ and let $W^{\prime}$ be the minimum vertex set where $B_{r}(P)=\text{tconv\,}(W^{\prime})$ . We are interested in finding the minimum enclosing ball, $B_{r}(P)$ . Recall that for any $x,y\in P$

d_{tr}(x,y)\leq\max_{i,j}d_{tr}(v_{i},v_{j})

where $v_{i},v_{j}\in V^{\prime}$ and $i,j\in[|V^{\prime}|]$ . Therefore,

\max_{i,j}d_{tr}(v_{i},v_{j})\leq\min_{k,l}d_{tr}(w_{k},w_{l}),

where $w_{k},w_{l}\in W^{\prime}$ and $k,l\in[|W^{\prime}|]$ . Considering $B_{r}(P)$ and $W^{\prime}$ ,

d_{tr}(w_{k},w_{l})=2r\;\;\forall\;k,l\in[|W^{\prime}|],

by definition of a tropical ball where $r$ is the radius of the the tropical ball. Therefore, since $B_{r}(P)$ encompasses $P$ ,

\max_{i,j}\frac{d_{tr}(v_{i},v_{j})}{2}\leq r.

∎

Example 3.13.

Consider the tropical polytope, $P$ , generated by $V=\{(0,0,0),\,(0,1,0),\,$
$(0,0,1)\}$ in $\mathbb{R}^{3}\!/\mathbb{R}{\bf 1}$ . The maximum pairwise tropical distance between the vertices is
$d_{tr}((0,1,0),(0,0,1))=2$ . Therefore, $r\geq 1$ (Figure 10 (left)).

Example 3.14.

Consider the tropical polytope, $P$ , generated by $V=\{(0,0,0),\,(0,2,5),\,$
$(0,3,1)\}$ in $\mathbb{R}^{3}\!/\mathbb{R}{\bf 1}$ . The maximum pairwise tropical distance between the vertices is $d_{tr}((0,0,0),$
$(0,2,5))=d_{tr}((0,3,1),(0,2,5))=5$ . Therefore $r\geq 2.5$ (Figure 10 (right)).

Example 3.15.

Consider the tropical polytope, $P$ , generated by $V=\{(0,-2,3),\,(0,-2,5),\,$
$(0,2,2),\,(0,1,1)\}$ in $\mathbb{R}^{3}\!/\mathbb{R}{\bf 1}$ . The maximum pairwise tropical distance between the vertices is $d_{tr}((0,-2,5),(0,1,0))=8$ . Therefore $r\geq 4$ (Figure 10 (bottom)).

Employing (14)-(16) in each of the previous examples shows that equality holds when using the result from Proposition 3.12. To show that equality does not always hold in (17), we provide the following example of a tropical polytope in $\mathbb{R}^{3}\!/\mathbb{R}{\bf 1}$ .

Example 3.16.

Consider the tropical polytope, $P$ , generated by four vertices $(0,0,0,0),\,(0,2,5,0),\,$
$(0,3,1,0),$ $\,(0,2,5,5)$ in $\mathbb{R}^{4}\!/\mathbb{R}{\bf 1}$ . The maximum pairwise tropical distance between the vertices is $d_{tr}((0,3,1,0),(0,2,5,5))=6$ . However, solving (14)-(15) yields $r=3.333$ with $y_{0}=(0,0,2,3.333,1.667)$ (Figure 11).

Knowing the $B_{r}(P)$ and $B_{R}(P)$ providess information about $P$ which we investigate further in Section 4.

4 Estimating the Volume of a Tropical Polytope

Estimating the volume of classical polytopes has wide application in math and science. As shown in many publications, finding exact volume of any convex body is challenging, especially in higher dimensions [20, 6]. A number of methods have been developed to estimate the volume of classical polytopes to include the use of Ehrhart theory as well as MCMC methods [10, 14]. In this section, we introduce a method to estimate the Euclidean volume of a tropical polytope using a HAR sampler with the tropical metric, an analogue of the method introduced in [10] for classical polytopes.

Remark 4.1.

As shown in [19], computing the volume of a tropical polytope, $Vol(P)$ , is NP-hard (see Theorem 5.5 and Corollary 5.6 in [19]). Further, if a tropical polytope is described by inequalities, calculating $Vol(P)$ is #P-hard [19, Theorem 8.1]. Additionally, we know that there is no polynomial time algorithm to approximate $Vol(P)$ unless $P=NP$ [19, Theorem 7.8]. Therefore, in general estimating $Vol(P)$ is a hard problem.

4.1 Volume of a Tropical Ball in Tropical Projective Space

In this section we apply $B_{r}(P)$ , whose volume can be computed analytically, to the problem of estimating the volume of a given tropical polytope. Ehrhart showed that the volume of a classical polytope can be determined by the leading coefficient of a rational quasi-polynomial for counting the number of lattice points inside of a dilated polytope [14]. Because a tropical ball, $B_{l}(x_{0})$ , is classically convex, we can calculate $Vol(B_{l}(x_{0}))$ by calculating the Ehrhart quasi-polynomial and determine its lead coefficient. Even more helpful is how a tropical ball, $B_{l}(x_{0})\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}$ , essentially consists of $e$ hypercubes where each edge of the hypercube is of length, $l$ . This structure allows us to calculate $Vol(B_{l}(x_{0}))$ using the following equation:

Vol(B_{l}(x_{0}))=e\times l^{(e-1)}.

(18)

Equation (18) was shown in [19, Corollary 3.3] and provides a straightforward calculation of $Vol(B_{l}(x_{0}))$ . Table 1 shows different values of $Vol(B_{l}(x_{0})$ of radius, $l=2$ and $l=4$ , with increasing dimension.

$n$	$Vol(B_{2}(x_{0}))$	$Vol(B_{4}(x_{0}))$
3	6	48
4	32	256
5	80	1280
6	192	6144
10	5120	$\approx 2.62\times 10^{6}$

Table 1: Volume of

B_{l}(x_{0})\in\mathbb{R}^{n}/\mathbb{R}\mathbf{1}

with increasing

n

for

l=2

and

l=4

4.2 Volume Estimation by Sampling from a Minimum Enclosing Ball

We estimate the volume of a given tropical polytope via sampling points from $B_{r}(P)$ enclosing $P$ and then determining the proportion, $p$ , of points that also fall inside of $P$ . Multiplying $Vol(B_{r}(P))$ by $p$ gives an estimate of $Vol(P)$ . Knowing $B_{r}(P)$ for any tropical polytope, $P$ , provides the bounds of $Vol(P)$ .

Proposition 4.2.

Let $P$ be a tropical polytope. Then $Vol(P)\leq Vol(B_{r}(P))$ . Specifically, $Vol(B_{r}(P))$ is an upper bound on $Vol(P)$ .

Proof.

By definition, $B_{r}(P)$ encloses $P$ . Therefore, $Vol(P)$ must be less than or equal to $Vol(B_{r}(P))$ , establishing an upper bound. ∎

Likewise, we can establish a lower bound for any tropical polytope with a $Tr_{e-1}(P)$ . In [19], the authors show the lower bound for a polytrope is the volume of the maximum inscribed ball (See Corollary 3.6). The following proposition is an extension to the general case.

Proposition 4.3.

Let $P$ be any tropical polytope containing a $Tr_{e-1}(P)$ where $e\geq 3$ . The $B_{R}(P)$ contained in $Tr_{e-1}(P)$ provides a lower bound on the volume of $P$ . Specifically,

Vol(P)\geq Vol(B_{R}(P))

Proof.

The $Tr_{e-1}(P)$ , of $P$ represents a tropical polytope of dimension $(e-1)$ [29]. Any tropical polytope, $P$ , where $dim(P)=(e-1)$ contains a $B_{R}(P)$ . Therefore, $B_{R}(P)$ of the $(e-1)$ -trunk, $B_{R}(Tr_{e-1}(P))=B_{R}(P)$ . Therefore,

Vol(B_{R}(P))=Vol(B_{R}(Tr_{e-1}(P))\leq Vol(P)).

∎

While Propositions 4.2 and 4.3 provide bounds on $Vol(P)$ , the range between these bounds can be very large.

Next we summarize our volume estimation technique. Given a tropical polytope $P\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}$ , calculate $B_{r}(P)$ . Using the HAR sampler described in A (see Algorithm 7), sample points from $B_{r}(P)$ . Determine the proportion $p$ , of sampled points from $B_{r}(P)$ that also fall in $P$ . Estimate $Vol(P)$ by the following calculation with $\cdot$ representing classical multiplication,

Vol(P)\approx p\cdot Vol(B_{r}(P)).

(19)

Algorithm 3 below describes these steps to estimates the volume of $P$ by sampling from $B_{r}(P)$ .

Algorithm 3 Volume Estimation of

P

by Sampling from

B_{r}(P)

Input: Tropical polytope

P:=\text{tconv\,}(v_{1},\ldots,v_{s})

; a minimum enclosing ball

B_{r}(P)

calculated using (14); an initial point

x_{0}\in\mathbb{R}/\mathbb{R}\mathbf{1}

and desired number of points

I

Output: Volume estimate of

P

Set

C=0

for

k=0,\ldots,I-1

, do

Generate random point

x_{k+1}

using Algorithm 7 in A.

x_{k+1}\in P

then

C=C+1

end if

end for

Set

p=\frac{C}{I}

Set

Vol(P)=p\cdot Vol(B_{r}(P))

return

Vol(P)

Because Algorithm 3 samples from $B_{r}(P)$ in order to estimate $Vol(P)$ , sampling more points from $B_{r}(P)$ will yield better results. Therefore, the number of points to sample is related to $Vol(B_{r}(P))$ relative to $Vol(Tr_{e-1}(P))$ . One way to evaluate this relationship is by comparing the ratio between the radii of $B_{R}(P)$ and $B_{r}(P)$ which is akin to a similar method described in [10] for classical polytopes. A small ratio suggests that $Vol(Tr_{e-1}(P))$ is relatively small compared $Vol(B_{r}(P))$ , requiring more sampled points to obtain a better estimate of $Vol(P)$ leading to the next proposition.

Proposition 4.4.

Given a minimum enclosing ball, $B_{r}(P)$ , and maximum inscribed ball, $B_{R}(P)$ , the rate, $A(P)$ , of sampled points from $B_{r}(P)$ falling inside $P$ is bounded below by,

A(P)\geq\left(\frac{R}{r}\right)^{(n-1)}.

(20)

Proof.

Consider two tropical balls, $B_{l}(x_{0})$ and $B_{k}(y_{0})$ , in $\mathbb{R}^{n}/\mathbb{R}\mathbf{1}$ such that $B_{l}(x_{0})\subset B_{k}(y_{0})$ . Recall that $Vol(B_{l}(x_{0}))$ and $Vol(B_{k}(y_{0}))$ are found using (18). Let,

$\displaystyle\frac{Vol(B_{l}(x_{0}))}{Vol(B_{k}(y_{0}))}$	$\displaystyle=\frac{nl^{n-1}}{nk^{n-1}}$	(21)
	$\displaystyle=\frac{l^{n-1}}{k^{n-1}}$	(22)
	$\displaystyle=\left(\frac{l}{k}\right)^{(n-1)}.$	(23)

Therefore we achieve the result. ∎

Proposition 4.2 helps provide insight to the difficulty in estimating $Vol(P)$ using Algorithm 3. Further, as $dim(P)$ increases, $Vol(B_{r}(P))$ increases as shown in Table 1, for a constant $r$ .

Example 4.5.

Consider the tropical polytope, $P$ , defined in Example 3.11 and shown in Figure 9. The maximum inscribed ball for $P$ has a radius, $R=0.5$ , indicating that $Vol(B_{R}(P))=0.5$ . The minimium enclosing ball of $P$ has a radius, $r=5$ , resulting in $Vol(B_{r}(P))=500$ . Employing Algorithm 3 in this case will involve sampling $B_{r}(P)$ where a $Vol(B_{r}(P))=500$ to estimate $Vol(P)$ that has a volume closer to $0.5$ .

Next, we offer some results using Algorithm 3 applied to some of the previously defined tropical polytopes.

Example 4.6 (Example 4.5 cont’d).

Consider the tropical polytope from Example 3.11. $B_{r}(P)$ has a radius of $r=5$ meaning that $Vol(B_{r}(P))=500$ . Table 2 shows the volume estimate using Algorithm 3 using increasing sample sizes. Here $I$ is the sample size and $C$ is the number of sampled points that fall in $P$ .

$I$	$C/I$	$Vol(P)$
1000	0.003	1.5
10000	0.0049	2.45
100000	0.00529	2.645

Table 2: Volume estimate of

P\in\mathbb{R}^{4}/\mathbb{R}\mathbf{1}

with varying number of sampled points,

I

, from

B_{r}(P)

Example 4.7 (Example 3.10, cont’d).

We apply Algorithm 3 to $P$ from Example 3.10, varying the number of sampled points taken from the $B_{r}(P)$ . Recall that $r=4$ for $B_{r}(P)$ meaning that $Vol(B_{r}(P))=48$ . Table 3 shows the estimate of $Vol(P)$ and Figure 12 illustrates the point dispersion for $I=1000$ and $I=10000$ .

$I$	$C/I$	$Vol(P)$
1000	0.168	8.064
10000	0.1993	9.564
100000	0.1965	9.4392

Table 3: Volume estimate of

P\in\mathbb{R}^{3}/\mathbb{R}\mathbf{1}

with varying number of sampled points,

I

, from

B_{r}(P)

4.3 Rounding a Tropical Polytope

In this section we consider the idea of “rounding” a tropical polytope in order to reduce the sample size needed to estimate $Vol(P)$ . In [10], rounding a classical polytope means applying a linear transformation to the polytope in near-isotropic position. This linear transformation reduces the difference between radii of the Euclidean maximum inscribed ball and the minimum enclosing ball for a classical polytope. This reduces the sample size required to estimate the volume of a given classical polytope [10].

In this section, we propose an analogue of this linear transformation to a tropical polytope $P$ . To do so, first, we identify a minimum enclosing tropical ball that only contains $Tr_{e-1}(P)$ denoted as $B_{k}(Tr_{e-1}(P))$ by removing all (e-2)-tentacles of $P$ such that only $Tr_{e-1}(P)$ remains. Since $Tr_{e-1}(P)\subseteq P$ , we have $B_{k}(Tr_{e-1}(P))\subseteq B_{r}(P)$ where $k\leq r$ . Therefore, we have

Vol(B_{k}(Tr_{e-1}(P)))\leq Vol(B_{r}(P)).

Thus, by removing all (e-2)-tentacles of $P$ , the minimum enclosing tropical ball, $B_{k}(Tr_{e-1}(P))$ , has smaller volume, requiring a smaller sample size to estimate $Vol(P)$ .

Here we will focus only on a tropical simplex $P_{\Delta}$ , that is not a polytrope but possesses a $Tr_{e-1}(P)$ (see Figure 9). For any $P_{\Delta}$ possessing $Tr_{e-1}(P_{\Delta})$ , $Tr_{e-1}(P_{\Delta})$ is classically convex. For the purposes of this paper, we begin with a vertex representation of $P_{\Delta}$ denoted as $v-representation(P_{\Delta})$ .

Algorithm 4 illustrates how to find $B_{k}(Tr_{e-1}(P_{\Delta}))$ . The algorithm involves enumerating pseudo-vertices which is known to be NP-hard for classical polyhedra with its hyperplane-representation [25].

Definition 4.8 (Pseudo-vertex (See [24])).

For a given $\mathcal{A}^{min}(V)$ , a pseudo-vertex of a $\max$ -tropical polytope $P$ , is any point, $x\in P$ coincident with the intersection of $(e-1)$ or more min-tropical hyperplanes.

To enumerate the pseudo-vertices of $Tr_{e-1}(P_{\Delta})$ , we first construct the $h^{*}-representation(P_{\Delta})$ of $P_{\Delta}$ . We then apply a double-description algorithm described in [3] and implemented by Fukuda in cddlib [16] where a double-description is defined as follows,

Definition 4.9 (Double Description Methods (See [1])).

A double description method is an algorithm that allows the computation of the vertex representation of a polyhedron that is defined by inequalities.

When using the double-description the $h^{*}-representation(P_{\Delta})$ is the input. Because the double-description algorithm is used to enumerate the vertices of classical polytopes described in hyperplane-representation, only the pseudo-vertices of the $Tr_{e-1}(P_{\Delta})$ will be enumerated since $Tr_{e-1}(P_{\Delta})$ is classically convex. By then applying (14)- (16) we can construct $B_{k}(Tr_{e-1}(P_{\Delta}))$ .

Algorithm 4 Rounding a tropical simplex,

P_{\Delta}

Input: Tropical simplex

P_{\Delta}:=\text{tconv\,}(v_{1},\ldots,v_{e})

Output: Minimum enclosing ball,

B_{k}(Tr_{e-1}(P_{\Delta}))

Construct the

h^{*}-representation(P_{\Delta})

Enumerate the set of pseudo-vertices defining

Tr_{e-1}(P_{\Delta})

using a

double-description

method [2].

Compute the minimum enclosing ball,

B_{k}(Tr_{e-1}(P_{\Delta}))

using (14)- (16).

return

B_{k}(Tr_{e-1}(P_{\Delta}))

The following example shows how to apply Algorithm 4 to a $P_{\Delta}$ that is not a polytrope.

Example 4.10 (Example 4.6 cont’d).

Consider the tropical polytope from Example 4.6. Note that this is also a tropical simplex, $P_{\Delta}$ . The $B_{r}(P_{\Delta})$ has radius $r=5$ meaning that $Vol(B_{r}(P_{\Delta}))=500$ . Proceeding through Algorithm 4, we get the following set of pseudo-vertices defining the boundary of $Tr_{e-1}(P_{\Delta})$ :

\left(\begin{array}[]{cccccccc}0&0&0&0&0&0&0&0\\ 0&0&0&0&1&1&1&1\\ 1&2&1&2&2&2&3&3\\ 4&4&6&7&5&7&5&8\\ \end{array}\right).

Computing the new minimum enclosing ball, $B_{k}(Tr_{e-1}(P_{\Delta}))$ , yields a radius, $r=2$ . This $B_{k}(Tr_{e-1}(P_{\Delta}))$ has a volume, $Vol(B_{r}(Tr_{e-1}(P_{\Delta})))=32$ . Figure 13 shows the resulting $Tr_{e-1}(P_{\Delta})\subset P_{\Delta}$ .

Table 4 compares the estimate of $Vol(P_{\Delta})$ before and after rounding.

$I$	$Vol(P_{\Delta})$	$Vol(Tr_{(e-1)}(P_{\Delta}))$
1000	1.5	2.752
10000	2.45	2.512
100000	2.645	2.517

Table 4: Volume estimates of

P_{\Delta},Tr_{e-1}(P_{\Delta})\in\mathbb{R}^{4}/\mathbb{R}\mathbf{1}

with varying number of sampled points,

I

for Example 4.10.

5 Sampling from a Union of Tropical Simplices in a Tropical Polytope

In this section, we focus on uniform sampling from $Tr_{e-1}(P)\subseteq P$ that is not classically convex where $P$ is a tropical polytope. Our goal is to identify a set of tropical simplices in $\Delta_{P}$ , such that the union of these tropical simplices define $Tr_{e-1}(P)$ . Then, using Algorithm 7 in A, sample from each tropical simplex according to the proportion of $Tr_{e-1}(P)$ they define. In [38], the authors show that uniform sampling from a polytrope is possible though do not implement the method. This can be extended to any tropical simplex, $P_{\Delta}$ , that is not contained within a tropical hyperplane (See Lemma 2 in [24]).

Unfortunately, for a $Tr_{e-1}(P)\in P$ that is not classically convex, we cannot apply Algorithm 7 directly due to biased sampling of the boundary of $P$ , denoted as $\partial P$ . Instead, given a vertex set, $V$ defining $P$ , where $|V|=n$ and $n>e$ , we must consider all $\binom{n}{e}$ combinations of $e$ vertices in $V$ . Each combination defines a tropical simplex, $P_{\Delta}^{i}\in\Delta_{P}$ where $\bigcup_{i=1}^{\binom{n}{e}}P_{\Delta}^{i}=P$ , which also defines $Tr_{(e-1)}(P)$ .

Once we enumerate each $P_{\Delta}^{i}\in\Delta_{P}$ , we must find a subset of tropical simplices, $\Delta_{P}^{\prime}\subset\Delta_{P}$ , such that $\bigcup_{k\in[|\Delta_{P}^{\prime}|]}P_{\Delta}^{k}=P^{\prime}\subseteq P$ where $Tr_{(e-1)}(P)\subset P^{\prime}$ and $0\leq dim(P_{\Delta}^{i}\cap P_{\Delta}^{j})\leq e-2$ for all $P_{\Delta}^{i},P_{\Delta}^{j}\subseteq\Delta_{P}^{\prime}$ . To find $\Delta_{P}^{\prime}$ , we can use Algorithm 7 to sample from $B_{r}(P)$ and identify those points of the entire sample, $X$ , that fall inside of $P$ . The sampled points that fall in $P$ we call $X_{P}$ . We then determine the proportion, $p_{i}$ , of points in $X_{P}$ that fall in each $P_{\Delta}^{i}\in\Delta_{P}$ . Finally, we say $\Delta_{P}^{\prime}=\left\{P_{\Delta}^{i},\ldots,P_{\Delta}^{k}\right\}$ where $i,k\in\left[\left|\binom{n}{e}\right|\right]$ and $\sum\limits_{j\in\{i\ldots,k\}}p_{j}=1$ .

Algorithm 5 Identifying

\Delta_{P}^{\prime}\subset\Delta_{P}

such that

0\leq dim(P_{\Delta}^{i}\cap P_{\Delta}^{j})\leq e-2

\forall\;P_{\Delta}^{i},P_{\Delta}^{j}\subset\Delta_{P}^{\prime}

where

\bigcup_{k\in[|\Delta_{P}^{\prime}|]}P_{\Delta}^{k}=P^{\prime}

such that

Tr_{(e-1)}(P)\subset P^{\prime}

Input: Tropical polytope

P:=\text{tconv\,}(v_{1},\ldots,v_{e})

; starting point,

x_{0}

; sample size,

I

Output: A set of tropical simplices,

\Delta_{P}^{\prime}\in\Delta_{P}

and

\mathbf{p}=\{p_{i}\ldots p_{k}\}

where

i,k\in\left[\left|\binom{|V|}{e}\right|\right]

Sample

I

points from

B_{r}(P)

using Algorithm 7 and call this set

X

Let

X_{P}\subset X

where

X_{P}

is the subset of points that fall inside

P

Enumerate each tropical simplex

P_{\Delta}^{i}\subset P

For each

P_{\Delta}^{i}\subset P

calculate

\frac{|X_{P}\in P_{\Delta}^{i}|}{|X_{P}|}=p_{i}

Let

\Delta_{P}^{\prime}=\left\{P_{\Delta}^{i},\ldots,P_{\Delta}^{k}\right\}

where

P^{\prime}=\bigcup_{j\in\{i,\ldots,k\}}P_{\Delta}^{j}

such that

\sum\limits_{j\in\{i\ldots,k\}}p_{j}=1

return

\Delta_{P}^{\prime}

and

\mathbf{p}=\{p_{i}\ldots p_{k}\}

where

i,k\in[\left|\binom{n}{e}\right|]

After identifying $\Delta_{P}^{\prime}$ and $\mathbf{p}$ , we then employ Algorithm 7 again and sample each $P_{\Delta}^{i}\in\Delta_{P}^{\prime}$ according to its proportion $p_{i}\in\mathbf{P}$ as shown in Algorithm 6.

Algorithm 6 Uniform Sampling

Tr_{(e-1)}(P)\in P

, where

P\in\mathbb{R}^{e}/\mathbb{R}\mathbf{1}

and

Tr_{e-1}(P)

is not classically convex.

Input: A set of tropical simplices

\Delta_{P}^{\prime}=\left\{P_{\Delta}^{i},\ldots,P_{\Delta}^{k}\right\}

and

\mathbf{p}=\{p_{i},\ldots,p_{k}\}

where

i,k\in\left[\left|\binom{n}{e}\right|\right]

taken from Algorithm 5; starting point,

y_{0}

; and a sample size

J

Output: A set,

Y

, of points sampled uniformly from

Tr_{(e-1)}(P)

for

j=0\ldots J-1

Randomly select

P_{\Delta}^{i}\subset\Delta_{P}^{\prime}

according to proportions defined in

\mathbf{p}

Sample

y_{j+1}

from

P_{\Delta}^{i}

using Algorithm 7.

end for

return

Y

As an example, we refer back to Figure 6. Note that the vertex set, $V$ , defining $P\in\mathbb{R}^{3}/\mathbb{R}\mathbf{1}$ has a cardinality, $|V|=4$ . This results in $\binom{4}{3}$ tropical simplices to examine (See Figure 7). In this case, either the pair of tropical simplices on the left of Figure 7 or the right represent sets of tropical simplices that only intersect at their boundary but still define $Tr_{e-1}(P)$ . We will consider the pair of tropical simplices on the right in the following example.

Example 5.1.

Consider the tropical polytope $P=\{(0,-2,3),(0,-2,5),(0,2,2),(0,1,0)\}$ . The tropical polytope, $P$ , may be decomposed into the two tropical simplices, $P_{\Delta}^{1}=\{(0,-2,5),(0,-2,3),$
$(0,1,0)\})$ with $p_{1}=0.62$ and $P_{\Delta}^{2}=\{(0,-2,5),(0,1,0),(0,2,2)\})$ with $p_{2}=0.38$ . Using Algorithm 6 and setting the sample size, $I=2000$ , we sample $P_{\Delta}^{1}$ and $P_{\Delta}^{2}$ according to the proportions $p_{1}$ and $p_{2}$ . Figure 14 shows the results for this example.

Example 5.2.

Consider the tropical polytope $P=\{(0,0,2,0),(0,0,0,0),(0,4,-10,0),(0,3,-3,5),$
$(0,4,2,10)\}$ . Here $P$ may be decomposed into five tropical simplices. While there is more than one combination of tropical simplices that define $Tr_{e-1}(P)$ , we identify $P_{\Delta}^{1}=\{(0,0,2,0),(0,0,0,0),$
$(0,4,-10,0),(0,4,2,10)\}$ with $p_{1}=0.97$ and $P_{\Delta}^{2}=\{(0,0,0,0),(0,4,-10,0),(0,3,-3,5),(0,4,2,10)\}$ with $p_{2}=0.03$ . Using a sample size of, $I=3000$ , we sample $P_{\Delta}^{1}$ and $P_{\Delta}^{2}$ . Figure 15 shows the results for this example.

6 Conclusion

In this paper we show that computing the maximum inscribed and minimum enclosing tropical balls of a tropical polytope can be formulated as linear programming problems and then we applied these tropical balls of a tropical polytope to estimate the volume of and uniform sampling from the tropical polytope over $\mathbb{R}^{e}/\mathbb{R}{\bf 1}$ .

Gaubert and Marie MacCaig showed that even estimating the volume of a tropical polytope is NP-hard [19]. The method described here, despite being easily implemented, does not change the difficulty of estimating the volume of a tropical polytope. In addition to the difficulty of volume estimation, Murty and Oskoorouchi showed that for a given classical polytope $P$ with the vertex representation, i.e, the polytope as a convex hull of a finitely many set of vertices, and for a given point $x_{0}\in P$ , computing a radius of the largest ball inscribed in $P$ with $x_{0}$ as the center is NP-hard [31]. Therefore, this leads a following problem:

Problem 6.1.

What is the time complexity of computing the radius and its center of a maximum inscribed tropical ball given a tropical polytope as a tropical convex set of a finitely many points in $\mathbb{R}^{e}/\mathbb{R}{\bf 1}$ ?

Similary, Shenmaier proved that for a given classical polytope $P$ with the vertex presentation, finding a center and computing a radius of the smallest ball enclosing a polytope $P$ is NP-hard [33]. Thus we have the following open problem:

Problem 6.2.

What is the time complexity of computing the radius and its center of a minimum enclosing tropical ball given a tropical polytope as a tropical convex set of a finitely many points in $\mathbb{R}^{e}/\mathbb{R}{\bf 1}$ ?

Appendix A Vertex Hit-and-Run Sampling with Extrapolation

In this appendix we describe the MCMC HAR sampler used in Algorithms 3, 5 and 6. The sampler is defined as a Vertex HAR Sampler with Extrapolation algorithm. This type of sampler samples uniformly from the $(e-1)$ -trunk (see Definition 2.16) of tropical simplices and was originally described in [38]. Specifically, in a tropical simplex $P_{\Delta}:=\text{tconv\,}(v^{1},\ldots,v^{s})$ in $\mathbb{R}^{e}/\mathbb{R}{\bf 1}$ with minimal vertex set $V^{\prime}$ , an “extrapolated” point from $v^{i}\in V^{\prime}$ through a point $x$ is defined by the projection to the other vertices or $V^{\prime-i}=\{v^{1},\ldots,v^{i-1},v^{i+1},\ldots,v^{e}\}$ as

\pi_{V^{\prime-i}}(x):=\bigoplus_{\begin{subarray}{c}l=1\\ l\neq i\end{subarray}}^{e}\lambda_{l}\odot v^{l}~{}~{}{\rm where}~{}~{}\lambda_{l}\!=\!{\rm min}(x-v^{l}).

(24)

The authors show that sampling along the line segment $\Gamma_{\pi_{V^{\prime-i}}(x),v^{i}}$ , is done so uniformly. However, results showed that sampling was biased because, in general, $\Gamma_{\pi_{V^{\prime-i}}(x),v^{i}}$ intersects the boundary of $P_{\Delta}$ , or $\partial P_{\Delta}$ , prior to reaching $v^{i}$ leading to oversampling of $\partial P_{\Delta}$ .

To avoid biased sampling of $\partial P_{\Delta}$ , we must detect when $\Gamma_{\pi_{V^{-i}}(x),v^{i}}$ , intersects $\partial P_{\Delta}$ and ignore the portion of $\Gamma_{\pi_{V^{-i}}(x),v^{i}}$ that continues on $\partial P_{\Delta}$ past the initial intersection. This ensures that the line segment from which we sample lies in the interior of $P$ preventing oversampling $\partial P_{\Delta}$ . While one of the end points of this line segment will be $\pi_{V^{-i}}(x)$ , the other will be one of the bend points of $\Gamma_{\pi_{V^{-i}}(x),v^{i}}$ .

Definition A.1 (Bend point from [30]).

Given two points $v^{1},\,v^{2}$ , a tropical line segment between $v^{1},\,v^{2}$ denoted as $\Gamma_{v^{1},v^{2}}$ , consists of the concatenation of at most $e-1$ Euclidean line segments. The collection of points $B$ , defining each Euclidean line segment are called the bend points of $\Gamma_{v^{1},v^{2}}$ . Including $v^{1}$ and $v^{2}$ , $\Gamma_{v^{1},v^{2}}$ consists of at most $e$ bend points. To compute the set $B$ defining $\Gamma_{v^{1},v^{2}}$ we have the following

B=\left\{\begin{array}[]{ccl}\!\!\!(v_{e}\!-\!u_{e})\odot u\oplus v\!\!\!\!&=&\!\!\!v\\ \!\!\!(v_{e-1}\!-\!u_{e-1})\odot u\oplus v\!\!\!\!&=&\!\!\!(v_{1},v_{2},v_{3},\ldots,v_{e-1},v_{e-1}-u_{e-1}+u_{e})\\ &\vdots&\\ \!\!\!(v_{2}\!-\!u_{2})\odot u\oplus v\!\!\!\!&=&\!\!\!(v_{1},v_{2},v_{2}-u_{2}+u_{3},\ldots,v_{2}-u_{2}+u_{e})\\ \!\!\!(v_{1}\!-\!u_{1})\odot u\oplus v\!\!\!\!&=&\!\!\!u.\\ \end{array}\right\}.

(25)

Therefore, using the fact that the boundary of the $Tr_{(e-1)}(P_{\Delta})$ in a tropical simplex, $P_{\Delta}$ is the intersection of closed sectors in $\mathcal{A}(V^{\prime})$ , we can detect the intersection of $\Gamma_{\pi_{V^{\prime-i}}(x),v^{i}}$ , with $\partial P_{\Delta}$ by successively evaluating the distance from each bend point, $b^{j}\in B$ , of $\Gamma_{\pi_{V^{\prime-i}}(x),v^{i}}$ to each $H_{\omega^{i}}^{min}$ . We compute this distance using Equation (26)

d_{tr}(x,H_{\omega^{i}}^{min})=d_{tr}(x+\omega,H_{\mathbf{0}}^{min}),

(26)

which is shown to be true in [18]. If $d_{tr}(b^{j},H_{\omega^{i}}^{min})=0$ for any $\omega^{i}$ , then $\partial P_{\Delta}$ has been detected. We then can truncate $\Gamma_{\pi_{V^{\prime-i}}(x),v^{i}}$ to $\Gamma_{\pi_{V^{\prime-i}}(x),b^{j}}$ and sample from $\Gamma_{\pi_{V^{\prime-i}}(x),b^{j}}$ using Algorithm 1 from [38]. If $\partial P_{\Delta}$ is not detected for any $b_{j}\in B$ , then we use Algorithm 1 from [38] to sample along the entirety of $\Gamma_{\pi_{V^{\prime-i}}(x),v^{i}}$ . This leads to Algorithm 7, which randomly subsets $V^{\prime}$ into subsets, $V^{\prime-i}$ and $\{v^{i}\}$ and only samples between $\pi_{V^{\prime-i}}(x)$ and the first intersection of $\Gamma_{\pi_{V^{\prime-i}}(x),v^{i}}$ with $\partial P_{\Delta}$ .

Algorithm 7 Vertex HAR extrapolation sampling from

P

with truncation using hyperplane distance calculation.

Input:

P_{\Delta}:=\text{tconv\,}(v^{1},\ldots,v^{s})

, an initial point

x_{0}\in P_{\Delta}

and maximum iteration

I\geq 1

Output: A random point

x\in P_{\Delta}

Let,

\Omega

, be the the set of normal vectors,

\omega^{i}

, defining

H^{\min}_{\omega^{i}}

at each

v^{i}\in V^{\prime}

for

k=0,\ldots,I-1

, do

Randomly select a non-empty set

{V^{\prime}}_{k}^{-i}

with

v^{i}\notin{V^{\prime}}_{k}^{-i}

Construct

\Gamma_{\pi_{{V^{\prime}}_{k}^{-i}}(x_{k}),v^{i}}

Order the set of bend points,

B

, defining line segment

\Gamma_{\pi_{V_{k}^{-i}}(x_{k}),v^{i}}

, excluding the end points.

Set

j=1

while

j\leq|B|

Calculate

d_{tr}(b^{j},H^{\min}_{\omega^{i}})

for each

\omega^{i}\in\Omega

where

b^{j}\in B

using Equation (26).

d_{tr}(b^{j},H^{\min}_{\omega^{i}})=0

for some

\omega^{i}\in\Omega

then

Let

\Gamma^{k}=\Gamma_{\pi_{V_{k}^{-i}}(x_{k}),b^{j}}

else

j<|B|

then

Set

j=j+1

else

Let

\Gamma^{k}=\Gamma_{\pi_{V_{k}^{-i}}(x_{k}),v^{i}}

end if

end while

Generate a random point

x_{k+1}

from the tropical line segment

\Gamma^{k}

using Algorithm 1 from [38].

end for

return

x:=x_{I}

Example A.1.

Let $P_{\Delta}:=\text{tconv\,}(\{(0,-1,1),(0,0,0),(0,1,-1)\})$ . Figure 16 shows the results from sampling 2000 points from $P_{\Delta}$ using Algorithm 7.

Acknowledgement

The authors thank Profs. Michael Joswig and Ngoc Tran for useful conversations and discussions. RY and DB are partially supported from NSF DMS 1916037. KM is partially supported by JSPS KAKENHI Grant Numbers JP18K11485, JP22K19816, JP22H02364.

References

[1] Xavier Allamigeon, Stéphane Gaubert, and Eric Goubault. The tropical double description method. In Jean-Yves Marion and Thomas Schwentick, editors, 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science, pages 47–58, Nancy, France, March 2010. Inria Nancy Grand Est & Loria.
[2] David Avis and Komei Fukuda. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Sym Comput Geometry, 8:98–104, 01 1991.
[3] David Avis and Komei Fukuda. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete & Computational Geometry, 8:295–313, 01 1992.
[4] François Baccelli, Guy Cohen, G.J. Olsder, and Jean-Pierre Quadrat. Synchronization and linearity - an algebra for discrete event systems. The Journal of the Operational Research Society, 45, 01 1994.
[5] Marie-Charlotte Brandenburg, Sophia Elia, and Leon Zhang. Multivariate volume, ehrhart, and $h^{*}$ -polynomials of polytropes. J. Symb. Comput., 114(C):209–230, jan 2023.
[6] Augustin Chevallier, Frédéric Cazals, and Paul Fearnhead. Efficient computation of the volume of a polytope in high-dimensions using piecewise deterministic markov processes, 2022.
[7] K. L. Clarkson. Coresets, sparse greedy approximation, and the frank-wolfe algorithm. ACM Transactions on Algorithms, 6(4):63, 2010.
[8] K. L. Clarkson, E. Hazan, and D. P. Woodruff. Sublinear optimization for machine learning. J. ACM, 59(5):23:1–23:49, 2012.
[9] Andrei Comăneci and Michael Joswig. Tropical medians by transportation, 2022.
[10] Ben Cousins and Santosh Vempala. A practical volume algorithm. Mathematical Programming Computation, 8:133–160, 10 2016.
[11] M. Develin and B. Sturmfels. Tropical convexity. Documenta Math., 9:1–27, 2004.
[12] Anton Dochtermann, Michael Joswig, and Raman Sanyal. Tropical types and associated cellular resolutions. Journal of Algebra, 356(1):304–324, apr 2012.
[13] E. Ehrhart. Sur les polyèdres rationnels homothétiques á n dimensions. C. R. Acad. Sci. Paris, 254:616–618, 1962.
[14] Eugene Ehrhart. Geometrie diophantienne-sur les polyedres rationnels homothetiques an dimensions. Comptes Rendus Hebdomadaires Des Seances De L Academie Des Sciences, 254(4):616, 1962.
[15] G. Elekes. A geometric inequality and the complexity of computing volume. Discrete Comput. Geom., 1(4):289–292, 1986.
[16] Komei Fukuda. cddlib, 2020.
[17] Francisco Criado Gallart. Tropical bisectors and diameters of simplicial complexes, 2021. PhD Dissertation at Technischen Universität Berlin.
[18] B. Gärtner and M. Jaggi. Tropical support vector machines, 2006. ACS Technical Report. No.: ACS-TR-362502-01.
[19] Stéphane Gaubert and Marie MacCaig. Approximating the volume of tropical polytopes is difficult. International Journal of Algebra and Computation, 29(02):357–389, 2019.
[20] Cunjing Ge, Feifei Ma, and Jian Zhang. A fast and practical method to estimate volumes of convex polytopes. CoRR, abs/1401.0120, 2014.
[21] Charles J. Geyer, Glen D. Meeden, and incorporates code from cddlib written by Komei Fukuda. rcdd: Computational Geometry, 2021. R package version 1.5.
[22] A.G. Horvath and Z. Langi. Maximum volume polytopes inscribed in the unit sphere. Monatsh Math, 181:341–354, 2016.
[23] Michael Joswig. Essentials of Tropical Combinatorics. Springer, New York, NY, 2021.
[24] Michael Joswig and Katja Kulas. Tropical and ordinary convexity combined. Advances in Geometry, 10(2):333–352, 2010.
[25] Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, and Vladimir A. Gurvich. Generating all vertices of a polyhedron is hard. Discrete & Computational Geometry, 39:174–190, 2006.
[26] H. Konno, Y. Yajima, and A. Ban. Calculating a minimal sphere containing a polytope defined by a system of linear inequalities. Comput Optim Applic, 3:181–191, 1994.
[27] C. Kuo, J. P. Wares, and J. C. Kissinger. The apicomplexan whole-genome phylogeny: An analysis of incongruence among gene trees. Mol Biol Evol, 25(12):2689–2698, 2008.
[28] B. Lin, B. Sturmfels, X. Tang, and R. Yoshida. Convexity in tree spaces. SIAM Discrete Math, 3:2015–2038, 2017.
[29] Georg Loho and Matthias Schymura. Tropical ehrhart theory and tropical volume. Research in the Mathematical Sciences, 7:30, 12 2020.
[30] D. Maclagan and B. Sturmfels. Introduction to Tropical Geometry, volume 161 of Graduate Studies in Mathematics. Graduate Studies in Mathematics, 161, American Mathematical Society, Providence, RI, 2015.
[31] K.G. Murty and M.R. Oskoorouchi. Sphere methods for lp. Algorithmic Operations Research, 5:21–33, 2010.
[32] Robert Page, Ruriko Yoshida, and Leon Zhang. Tropical principal component analysis on the space of phylogenetic trees. Bioinformatics, 36(17):4590–4598, 06 2020.
[33] V.V. Shenmaier. The problem of a minimal ball enclosing k points. J. Appl. Ind. Math., 7:444–448, 2013.
[34] Ngoc Mai Tran. Polytropes and tropical eigenspaces: Cones of linearity. Discrete & Computational Geometry, 51:539–558, 2012.
[35] Ngoc Mai Tran. Enumerating polytropes. Journal of Combinatorial Theory, Series A, 151:1–22, 2017.
[36] R. Yoshida, L. Zhang, and X. Zhang. Tropical principal component analysis and its application to phylogenetics. Bulletin of Mathematical Biology, 81:568–597, 2019.
[37] Ruriko Yoshida, David Barnhill, Keiji Miura, and Daniel Howe. Tropical density estimation of phylogenetic trees, 2022.
[38] Ruriko Yoshida, Keiji Miura, and David Barnhill. Hit and run sampling from tropically convex sets, 2022.
[39] Ruriko Yoshida, Misaki Takamori, Hideyuki Matsumoto, and Keiji Miura. Tropical support vector machines: Evaluations and extension to function spaces. Neural Networks, 157:77–89, 2021.