BigObject VoronoiDiagram

from application tropical

Voronoi diagram with respect to the tropical metric in the tropical projective torus. Its combinatorics is controlled by a POLYTROPE_PARTITION. See P. Criado, M. Joswig, P. Santos: Tropical bisectors and Voronoi diagrams, arXiv:1906.10950

Example:

The following computes a tropical Voronoi diagram of three SITES in the tropical 3-torus.

 > $T= new VoronoiDiagram(SITES=>[[-4,-4,0,0],[-3,0,2,0],[-2,-5,-2,0]]);
 > print $T->POLYTROPE_PARTITION->size();
 134

AMBIENT_DIM

Number of dimensions of the diagram. One less than the number of coordinates.

Type:

Int

N_SITES

Number of sites of the diagram.

Type:

Int

POLYTROPE_PARTITION

Representation of the tropical Voronoi diagram. Each such polyhedron is a domain in which the distance to the set of sites $S$ is a minimum of linear functions. This list of regions is represented as an array of pairs of matrices. The first matrix in each pair represents the region itself (a polytrope) as a shortest path matrix. The second matrix (the labels) gives the index of the site $s\in S$ with maximum $s_j-s_i$ such that the cone $\{x:x_i-s_i<= x_k-s_k <= x_j-s_j \forall k\in [d+1]\}$ intersects this cell (or $-1$ if no such index exists). Then, in this region, $dist(x,S)$ is a minimum of the linear functions $(x_j-s_j)-(x_i-s_i)$ for each $s$ labelled with $(i,j)$.

Type:

Array<Pair<Matrix<Rational,NonSymmetric>,Matrix<Int,NonSymmetric>>>

Example:

Here is one polytrope cell.

 > $T= new VoronoiDiagram(SITES=>[[-4,-4,0,0],[-3,0,2,0],[-2,-5,-2,0]]);
 > print $T->POLYTROPE_PARTITION->[0];
 <0 inf inf inf
 -4 0 2 0
 -5 inf 0 inf
 -4 inf inf 0
 >
 <-1 1 -1 -1
 -1 -1 -1 -1
 -1 -1 -1 -1
 -1 -1 -1 -1
 >

SITES

The sites of the tropical Voronoi diagram.

Type:

Matrix<Rational,NonSymmetric>

VISUAL

UNDOCUMENTED