====== BigObject Polytope ====== //from application [[..:tropical|tropical]]//\\ \\ A tropical polytope is the tropical convex hull of finitely many points or the finite intersection of tropical halfspaces in a tropical projective space. Many combinatorial properties depend on ''[[..:tropical:Polytope#POINTS |POINTS]]''. Note: ''[[..:tropical:Polytope#VERTICES |VERTICES]]'' are used for ''[[..:tropical:Polytope#POINTS |POINTS]]'' if the tropical polytope is initialized by INEQUALITIES. ? Type Parameters: :: ''Addition'': Either ''[[..:common#Min |Min]]'' or ''[[..:common#Max |Max]]''. There is NO default for this, you have to choose! :: ''Scalar'': Rational by default. The underlying type of ordered group. ? Example: :: Constructing a tropical polygon from a fixed list of generators. :: > $P = new Polytope(POINTS=>[[0,1,0],[0,4,1],[0,3,3],[0,0,2]]); ? Example: :: Constructing the same tropical polygon from tropical linear inequalities. :: > $A1 = new Matrix>([[0,-2,"inf"],["inf",-4,"inf"],["inf",-3,-1],["inf","inf",-3],[0,"inf","inf"]]); > $A2 = new Matrix>([["inf","inf",-1],[0,"inf",-1],[0,"inf","inf"],[0,-1,"inf"],["inf",0,0]]); > $Q = new Polytope(INEQUALITIES=>[$A1,$A2]); > print $Q->VERTICES; 0 0 2 0 1 0 0 3 3 0 4 1 ? Permutations: : ? PointsPerm: :: permuting the ''[[..:tropical:Polytope#POINTS |POINTS]]'' ? VertexPerm: :: permuting the ''[[..:tropical:Polytope#VERTICES |VERTICES]]'' ===== Properties ===== ==== Input property ==== These properties are for input only. They allow redundant information. ---- {{anchor:inequalities:}} ? **''INEQUALITIES''** :: Inequalities giving rise to the polytope; redundancies are allowed. They must be encoded as a pair of matrices. The pair (A,B) encodes the inequality //A//x ~ //B//x, where ~ is <= for min and >= for max. All vectors in this section must be non-zero. Dual to ''[[..:tropical:Polytope#POINTS |POINTS]]''. Input section only. ? Type: :''[[..:common#Pair |Pair]]<[[..:common#Matrix |Matrix]]<[[..:common#TropicalNumber |TropicalNumber]],[[..:common#NonSymmetric |NonSymmetric]]>,[[..:common#Matrix |Matrix]]<[[..:common#TropicalNumber |TropicalNumber]],[[..:common#NonSymmetric |NonSymmetric]]%%>>%%'' ---- ==== Combinatorics ==== These properties capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice. ---- {{anchor:maximal_covectors:}} ? **''MAXIMAL_COVECTORS''** :: The covectors of the maximal cells of the torus subdivision. Entries correspond to rows of ''[[..:tropical:Polytope#MAXIMAL_COVECTOR_CELLS |MAXIMAL_COVECTOR_CELLS]]''. ? Type: :''[[..:common#Array |Array]]<[[..:common#IncidenceMatrix |IncidenceMatrix]]<[[..:common#NonSymmetric |NonSymmetric]]%%>>%%'' ---- {{anchor:maximal_covector_cells:}} ? **''MAXIMAL_COVECTOR_CELLS''** :: These are the maximal cells of the covector decomposition of the tropical torus with respect to ''[[..:tropical:Polytope#POINTS |POINTS]]''. Each row corresponds to a maximal cell, each column to an element of ''[[..:tropical:Polytope#PSEUDOVERTICES |PSEUDOVERTICES]]''. ? Type: :''[[..:common#IncidenceMatrix |IncidenceMatrix]]<[[..:common#NonSymmetric |NonSymmetric]]>'' ---- {{anchor:polytope_covector_decomposition:}} ? **''POLYTOPE_COVECTOR_DECOMPOSITION''** :: This is a sublattice of ''[[..:tropical:Polytope#TORUS_COVECTOR_DECOMPOSITION |TORUS_COVECTOR_DECOMPOSITION]]'', containing only the cells that belong to the tropical span of ''[[..:tropical:Polytope#POINTS |POINTS]]''. ? Type: :''[[..:tropical:CovectorLattice |CovectorLattice]]'' ---- {{anchor:polytope_maximal_covectors:}} ? **''POLYTOPE_MAXIMAL_COVECTORS''** :: The covectors of the maximal cells of the polytope subdivision. Entries correspond to rows of ''[[..:tropical:Polytope#POLYTOPE_MAXIMAL_COVECTOR_CELLS |POLYTOPE_MAXIMAL_COVECTOR_CELLS]]''. ? Type: :''[[..:common#Array |Array]]<[[..:common#IncidenceMatrix |IncidenceMatrix]]<[[..:common#NonSymmetric |NonSymmetric]]%%>>%%'' ---- {{anchor:polytope_maximal_covector_cells:}} ? **''POLYTOPE_MAXIMAL_COVECTOR_CELLS''** :: This is a description of the tropical polytope as a polyhedral complex. Each row is a maximal cell of the covector subdivision of the tropical polytope. Indices refer to ''[[..:tropical:Polytope#PSEUDOVERTICES |PSEUDOVERTICES]]''. ? Type: :''[[..:common#IncidenceMatrix |IncidenceMatrix]]<[[..:common#NonSymmetric |NonSymmetric]]>'' ---- {{anchor:pseudovertex_coarse_covectors:}} ? **''PSEUDOVERTEX_COARSE_COVECTORS''** :: Coarse types of ''[[..:tropical:Polytope#PSEUDOVERTICES |PSEUDOVERTICES]]'' relative to ''[[..:tropical:Polytope#POINTS |POINTS]]''. Each row corresponds to a row of ''[[..:tropical:Polytope#PSEUDOVERTICES |PSEUDOVERTICES]]'' and encodes at position i, how many ''[[..:tropical:Polytope#POINTS |POINTS]]'' contain that pseudovertex in the i-th sector. ? Type: :''[[..:common#Matrix |Matrix]]<[[..:common#Int |Int]],[[..:common#NonSymmetric |NonSymmetric]]>'' ---- {{anchor:pseudovertex_covectors:}} ? **''PSEUDOVERTEX_COVECTORS''** :: Types of ''[[..:tropical:Polytope#PSEUDOVERTICES |PSEUDOVERTICES]]'' relative to ''[[..:tropical:Polytope#POINTS |POINTS]]''. Each type is encoded as an Incidence matrix, where rows correspond to coordinates and columns to ''[[..:tropical:Polytope#POINTS |POINTS]]''. If the i-th row is a set S, that means that this pseudovertex is in the i-th sector of all points indexed by S. For bounded vertices, the type is computed as usual. For unbounded rays (i.e. starting with a 0), the type is computed as follows. Let g be a generator, with infinite entries at positions J and let the ray be e_J = sum_{j in J} +- e_j (the sign being the orientation of the addition). If J is contained in K, the ray is "contained" in all sectors of g. Otherwise, the ray is "contained" in the sectors indexed by g. NOTE: The latter is an artificial definition in the sense that it is not compatible with intersecting faces of the covector lattice. However, it is correct in the sense that faces spanned by a list of pseudovertices have as covector the intersection of the respective covectors. ? Type: :''[[..:common#Array |Array]]<[[..:common#IncidenceMatrix |IncidenceMatrix]]<[[..:common#NonSymmetric |NonSymmetric]]%%>>%%'' ---- {{anchor:torus_covector_decomposition:}} ? **''TORUS_COVECTOR_DECOMPOSITION''** :: This is the face lattice of the polyhedral complex, whose vertices are ''[[..:tropical:Polytope#PSEUDOVERTICES |PSEUDOVERTICES]]'' and whose cells are the cells of the covector decomposition. For each face in this lattice, we save the following information: 1) What PSEUDOVERTICES make up this face, i.e. a Set 2) What is the covector of this face, i.e. an IncidenceMatrix (whose rows correspond to coordinates and whose columns to ''[[..:tropical:Polytope#POINTS |POINTS]]''). NOTE: This lattice does not contain any far faces of the polyhedral cells, as they do not have well-defined covectors. ? Type: :''[[..:tropical:CovectorLattice |CovectorLattice]]'' ---- ==== Geometry ==== These properties capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets. ---- {{anchor:dome:}} ? **''DOME''** :: This is the dome of the tropical hyperplane arrangement defined by the ''[[..:polytope:Polytope#POINTS |POINTS]]''. I.e. we take as function the (tropical) product of the tropical linear polynomials defined in the following manner: For each point (p_0,...,p_d) we get the linear polynomial sum_{i=1}^d (1/p_i) * x_i, where sum is the DUAL tropical addition and * and / is regular addition and subtraction, respectively. ? Type: :''[[..:polytope:Polytope |Polytope]]'' ---- {{anchor:envelope:}} ? **''ENVELOPE''** :: Tropical polytopes have a natural description as the complex of certain faces of their envelopes. This envelope depends on the choice of the ''[[..:polytope:Polytope#POINTS |POINTS]]'' that generate the tropical polytope. ? Type: :''[[..:polytope:Polytope |Polytope]]'' ---- {{anchor:far_pseudovertices:}} ? **''FAR_PSEUDOVERTICES''** :: Subset of the ''[[..:tropical:Polytope#PSEUDOVERTICES |PSEUDOVERTICES]]'' which are not contained in the tropical projective torus. ? Type: :''[[..:common#Set |Set]]<[[..:common#Int |Int]]>'' ---- {{anchor:feasible:}} ? **''FEASIBLE''** :: True if the polyhedron is not empty. ? Type: :''[[..:common#Bool |Bool]]'' ---- {{anchor:points:}} ? **''POINTS''** :: Input points in tropical homogeneous coordinates. This is the fixed system of generators with respect to which many combinatorial properties are expressed. ? Type: :''[[..:common#Matrix |Matrix]]<[[..:common#TropicalNumber |TropicalNumber]],[[..:common#NonSymmetric |NonSymmetric]]>'' ---- {{anchor:projective_ambient_dim:}} ? **''PROJECTIVE_AMBIENT_DIM''** :: Dimension of the tropical projective space which contains the tropical polytope. ? Type: :''[[..:common#Int |Int]]'' ---- {{anchor:pseudovertices:}} ? **''PSEUDOVERTICES''** :: Pseudovertices are the vertices of the type decomposition of the tropical torus induced by ''[[..:tropical:Polytope#POINTS |POINTS]]''. They are projections of the vertices of ''[[..:tropical:Polytope#ENVELOPE |ENVELOPE]]''. Note that each pseudovertex is given in tropical homogeneous coordinates with a leading 1 or 0, depending on whether it is a vertex or a ray. ? Type: :''[[..:common#Matrix |Matrix]]'' ---- {{anchor:valid_point:}} ? **''VALID_POINT''** :: Some point belonging to the polyhedron. ? Type: :''[[..:common#Vector |Vector]]<[[..:common#TropicalNumber |TropicalNumber]]>%%'' ---- {{anchor:vertices:}} ? **''VERTICES''** :: Vertices of the tropical convex hull, a submatrix of ''[[..:tropical:Polytope#POINTS |POINTS]]'' ? Type: :''[[..:common#Matrix |Matrix]]<[[..:common#TropicalNumber |TropicalNumber]],[[..:common#NonSymmetric |NonSymmetric]]>'' ---- {{anchor:vertices_in_points:}} ? **''VERTICES_IN_POINTS''** :: Entries correspond to ''[[..:tropical:Polytope#VERTICES |VERTICES]]''. They describe for each vertex, what its row index in ''[[..:tropical:Polytope#POINTS |POINTS]]'' is. ? Type: :''[[..:common#Array |Array]]<[[..:common#Int |Int]]>'' ---- ===== Methods ===== ==== Geometry ==== These methods capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets. ---- {{anchor:polytope_subdivision_as_complex:}} ? **''polytope_subdivision_as_complex([[..:common#Int |Int]] chart)''** :: This returns the subdivision of the polytope induced by ''[[..:tropical:Polytope#POINTS |POINTS]]'' as a polyhedral complex on a chosen affine chart. ? Parameters: :: ''[[..:common#Int |Int]]'' ''chart'': Which coordinate to normalize to 0. This is 0 by default. ? Returns: :''[[..:fan:PolyhedralComplex |PolyhedralComplex]]'' ---- {{anchor:torus_subdivision_as_complex:}} ? **''torus_subdivision_as_complex([[..:common#Int |Int]] chart)''** :: This returns the subdivision of the tropical torus induced by ''[[..:tropical:Polytope#POINTS |POINTS]]'' as a polyhedral complex on a chosen affine chart ? Parameters: :: ''[[..:common#Int |Int]]'' ''chart'': Which coordinate to normalize to 0. This is 0 by default. ? Returns: :''[[..:fan:PolyhedralComplex |PolyhedralComplex]]'' ---- ==== Visualization ==== These methods are for visualization. ---- {{anchor:visual:}} ? **''VISUAL()''** :: Visualize the subdivision of the polytope induced by ''[[..:tropical:Polytope#POINTS |POINTS]]''. ? Returns: :''[[..:fan:Visual_PolyhedralFan |Visual::PolyhedralFan]]'' ---- {{anchor:visual_hyperplane_arrangement:}} ? **''VISUAL_HYPERPLANE_ARRANGEMENT()''** :: Visualize the arrangement of hyperplanes with apices in the ''[[..:tropical:Polytope#POINTS |POINTS]]'' of the tropical polytope. ? Options: : option list ''[[..:common#Visual_Polygons_decorations |Visual::Polygons::decorations]]'' ? Returns: :''[[..:fan:Visual_PolyhedralFan |Visual::PolyhedralFan]]'' ---- {{anchor:visual_subdivision:}} ? **''VISUAL_SUBDIVISION()''** :: Visualize the subdivision of the torus induced by ''[[..:tropical:Polytope#POINTS |POINTS]]''. ? Returns: :''[[..:fan:Visual_PolyhedralFan |Visual::PolyhedralFan]]'' ----