1#  Copyright (c) 1997-2021
2#  Ewgenij Gawrilow, Michael Joswig, and the polymake team
3#  Technische Universität Berlin, Germany
4#  https://polymake.org
5#
6#  This program is free software; you can redistribute it and/or modify it
7#  under the terms of the GNU General Public License as published by the
8#  Free Software Foundation; either version 2, or (at your option) any
9#  later version: http://www.gnu.org/licenses/gpl.txt.
10#
11#  This program is distributed in the hope that it will be useful,
12#  but WITHOUT ANY WARRANTY; without even the implied warranty of
13#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14#  GNU General Public License for more details.
15#-------------------------------------------------------------------------------
16
17package Visual::TVD;
18
19# cutoff factor for visualizing a tropical Voronoi diagram
20custom $cutoff=new Rational(20);
21
22
23# Voronoi diagram with respect to the tropical metric in the tropical projective torus.
24# Its combinatorics is controlled by a [[POLYTROPE_PARTITION]].
25# See P. Criado, M. Joswig, P. Santos: Tropical bisectors and Voronoi diagrams, arXiv:1906.10950
26#
27# @example The following computes a tropical Voronoi diagram of three [[SITES]] in the tropical 3-torus.
28# > $T= new VoronoiDiagram(SITES=>[[-4,-4,0,0],[-3,0,2,0],[-2,-5,-2,0]]);
29# > print $T->POLYTROPE_PARTITION->size();
30# | 134
31declare object VoronoiDiagram {
32
33  file_suffix tvd
34
35  # The sites of the tropical Voronoi diagram.
36  property SITES : Matrix<Rational>;
37
38  # Number of sites of the diagram.
39  property N_SITES : Int;
40
41  rule N_SITES : SITES {
42    $this->N_SITES= $this->SITES->rows;
43  }
44
45  # Number of dimensions of the diagram. One less than the number of coordinates.
46  property AMBIENT_DIM : Int;
47
48  rule AMBIENT_DIM : SITES {
49    $this->AMBIENT_DIM= $this->SITES->cols-1;
50  }
51
52  # Representation of the tropical Voronoi diagram.
53  # Each such polyhedron is a domain in which the distance to the set of sites $S$ is a minimum of linear functions.
54  # This list of regions is represented as an array of pairs of matrices.
55  # The first matrix in each pair represents the region itself (a polytrope) as a shortest path matrix.
56  # 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).
57  # 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)$.
58  # @example Here is one polytrope cell.
59  # > $T= new VoronoiDiagram(SITES=>[[-4,-4,0,0],[-3,0,2,0],[-2,-5,-2,0]]);
60  # > print $T->POLYTROPE_PARTITION->[0];
61  # | <0 inf inf inf
62  # | -4 0 2 0
63  # | -5 inf 0 inf
64  # | -4 inf inf 0
65  # | >
66  # | <-1 1 -1 -1
67  # | -1 -1 -1 -1
68  # | -1 -1 -1 -1
69  # | -1 -1 -1 -1
70  # | >
71  property POLYTROPE_PARTITION : Array<Pair<Matrix<Rational>, Matrix<Int>>>;
72
73  rule POLYTROPE_PARTITION : SITES {
74      compute_polytrope_partition($this);
75  }
76
77  user_method VISUAL : AMBIENT_DIM, SITES, POLYTROPE_PARTITION {
78      my $this= shift;
79
80      my @result = visualizable_cells($this->SITES, $this->AMBIENT_DIM, $this->POLYTROPE_PARTITION, $Visual::TVD::cutoff);
81      compose(map {$_->VISUAL} @result);
82  }
83}
84
85# Local Variables:
86# mode: perl
87# cperl-indent-level: 3
88# indent-tabs-mode:nil
89# End:
90