Download Algorithmic aspects of tropical intersection theory

1.3. Preliminaries
https://bitbucket.org/hampe/atint
(see Chapter 8 for more details).
Most of Part I can be found in
S. Hampe, a-tint: A polymake extension for algorithmic tropical intersection theory, European J. of Combinatorics, 36C (2014), pp. 579-607
The results of Part II will be published on the arXiv in spring 2014.
1.3. Preliminaries
1.3.1. Polyhedra and polyhedral complexes
Let Λ ≅ Zn be a lattice and denote by VΛ = Λ ⊗ R ≅ Rn its associated vector space.
A rational polyhedron or polyhedral cell in VΛ is a set of the form
σ = {x ∶ gi (x) ≥ αi ; i = 1, . . . , s}
where gi ∈ Λ∨ and αi ∈ R for i = 1, . . . , s, i.e. it is an intersection of finitely many
halfspaces. We call σ a cone if we can choose a representation such that αi = 0 for all
i.
Equivalently, any polyhedron σ can be described as
σ = conv{p1 , . . . , pk } + R≥0 r1 + ⋅ ⋅ ⋅ + R≥0 rl + L
where p1 , . . . , pk , r1 , . . . , rl ∈ Rn , L is a linear subspace of Rn and + denotes the
Minkowski sum of sets:
A + B = {a + b; a ∈ A, b ∈ B}.
The first description is often called an H-description of σ and the second is a Vdescription of σ.
It is a well known algorithmic problem in convex geometry to compute one of these
descriptions from the other. In fact, both directions are computationally equivalent
and there are several well-known convex-hull-algorithms. Most notable are the doubledescription method [MRTT], the reverse search method [AF] and the beneath-andbeyond algorithm (e.g. [G],[E]). Generally speaking, each of these algorithms behaves
very well in terms of complexity for a certain class of polyhedra, but very badly
for some other types (see [ABS] for a more in-depth discussion of this). Since in
tropical geometry all kinds of polyhedra can occur, it is very difficult to pick an optimal
algorithm. It is also an open problem, whether there exists a convex hull algorithm
with polynomial complexity in both input and output. All of the above mentioned
algorithms are implemented in polymake or in libraries used by polymake. At the
moment, all algorithms in a-tint use the implementation of the double-description
algorithm by Fukuda [F].
13