Changeset 16ed2f in git


Ignore:
Timestamp:
Mar 25, 2009, 12:31:32 PM (14 years ago)
Author:
Thomas Markwig <keilen@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a800fe4b3e9d37a38c5a10cc0ae9dfa0c15a4ee6')
Children:
66a5f833d02d3288ce452e48c6ece435a1f9ebd0
Parents:
087a94afc4dc0923c87d4d3d336e0ab8ae621a77
Message:
Alle Zeilen auf 80 Zeichen beschraenkt.


git-svn-id: file:///usr/local/Singular/svn/trunk@11590 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed

  • Singular/LIB/polymake.lib

    r087a94 r16ed2f  
    1 version="$Id: polymake.lib,v 1.11 2009-03-16 11:34:10 keilen Exp $";
     1version="$Id: polymake.lib,v 1.12 2009-03-25 11:31:32 keilen Exp $";
    22category="Tropical Geometry";
    33info="
    4 LIBRARY:        polymake.lib    Computations with polytopes and fans, interface to polymake and TOPCOM
    5 AUTHOR:         Thomas Markwig,  email: keilen@mathematik.uni-kl.de
     4LIBRARY:   polymake.lib    Computations with polytopes and fans,
     5                           interface to polymake and TOPCOM
     6AUTHOR:    Thomas Markwig,  email: keilen@mathematik.uni-kl.de
    67
    78WARNING:
    8      Most procedures will not work unless polymake or topcom is installed and
    9      if so, they will only work with the operating system LINUX!
    10      For more detailed information see IMPORTANT NOTE respectively consult the
    11      help string of the procedures.
     9   Most procedures will not work unless polymake or topcom is installed and
     10   if so, they will only work with the operating system LINUX!
     11   For more detailed information see IMPORTANT NOTE respectively consult the
     12   help string of the procedures.
    1213
    1314IMPORTANT NOTE:
    14      Even though this is a Singular library for computing polytopes and fans such
    15      as the Newton polytope or the Groebner fan of a polynomial, most of the hard
    16      computations are NOT done by Singular but by the program
    17 @*   -  polymake by Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt
    18 @*      (see http://www.math.tu-berlin.de/polymake/),
    19 @*   respectively (only in the procedure triangularions) by the program
    20 @*   -  topcom by Joerg Rambau, Universitaet Bayreuth
    21 @*      (see http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM);
    22 @*   this library should rather be seen as an interface which allows to use a (very limited)
    23      number of options which polymake respectively topcom offers to compute with polytopes
    24      and fans and to make the results available in Singular for further computations;
    25      moreover, the user familiar with Singular does not have to learn the syntax of polymake
    26      or topcom, if the options offered here are sufficient for his purposes.
    27 @*   Note, though, that the procedures concerned with planar polygons are independent of
    28      both, polymake and topcom.
     15   Even though this is a Singular library for computing polytopes and fans
     16   such as the Newton polytope or the Groebner fan of a polynomial, most of
     17   the hard computations are NOT done by Singular but by the program
     18@* - polymake by Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt
     19@*   (see http://www.math.tu-berlin.de/polymake/), 
     20@* respectively (only in the procedure triangularions) by the program
     21@* - topcom by Joerg Rambau, Universitaet Bayreuth (see
     22@*   http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM);
     23@*   this library should rather be seen as an interface which allows to use a
     24     (very limited) number of options which polymake respectively topcom offers
     25     to compute with polytopes and fans and to make the results available in
     26     Singular for further computations;
     27     moreover, the user familiar with Singular does not have to learn the syntax
     28     of polymake or topcom, if the options offered here are sufficient for his
     29     purposes.
     30@*   Note, though, that the procedures concerned with planar polygons are
     31     independent of both, polymake and topcom.
    2932
    3033PROCEDURES USING POLYMAKE:
    31      polymakePolytope(list)            computes the vertices of a polytope using polymake
    32      newtonPolytope(poly)              computes the Newton polytope of the polynomial
    33      newtonPolytopeLP(poly)            computes the lattice points of the Newton polytope of the polynomial
    34      normalFan(intmat,intmat,list)     computes the normal fan of a polytope
    35      groebnerFan(poly)                 computes the Groebner fan of a polynomial
    36      intmatToPolymake(intmat,string)   transforms an integer matrix into polymake format
    37      polymakeToIntmat(string,string)   transforms polymake output into an integer matrix
     34  polymakePolytope   computes the vertices of a polytope using polymake
     35  newtonPolytope     computes the Newton polytope of a polynomial
     36  newtonPolytopeLP   computes the lattice points of the Newton polytope
     37  normalFan          computes the normal fan of a polytope
     38  groebnerFan        computes the Groebner fan of a polynomial
     39  intmatToPolymake   transforms an integer matrix into polymake format
     40  polymakeToIntmat   transforms polymake output into an integer matrix
    3841
    3942PROCEDURES USING TOPCOM:
    40      triangulations(list)          computes all triangulations of a marked polytope
    41      secondaryPolytope(list)       computes the secondary polytope of a marked polytope
     43  triangulations     computes all triangulations of a marked polytope
     44  secondaryPolytope  computes the secondary polytope of a marked polytope
    4245
    4346PROCEDURES USING POLYMAKE AND TOPCOM:
    44      secondaryFan(list)            computes the secondary fan of a marked polytope
     47  secondaryFan       computes the secondary fan of a marked polytope
    4548
    4649PROCEDURES CONERNED WITH PLANAR POLYGONS:
    47      cycleLength(list,intvec)      computes the cycleLength of cycle dual to list with interior point intvec
    48      splitPolygon(list)            splits a marked polygon into vertices, facets and interior points
    49      eta(list,list)                computes the eta-vector of a triangulation
    50      findOrientedBoundary(list)    computes the boundary of the convex hull of a list of lattice points
    51      cyclePoints(list,list,int)    computes lattice points connected to a lattice point in a triangulation
    52      latticeArea(list)             computes the lattice area of a polygon
    53      picksFormula(list)            computes the ingrediants of Pick's formula for a polygon
    54      ellipticNF(list)              computes the normal form of an elliptic polygon
    55      ellipticNFDB(int)             displays the 16 normal forms of elliptic polygons
     50  cycleLength      computes the cycleLength of cycle
     51  splitPolygon     splits a marked polygon into vertices, facets, interior points
     52  eta              computes the eta-vector of a triangulation
     53  findOrientedBoundary    computes the boundary of a convex hull
     54  cyclePoints      computes lattice points connected to some lattice point
     55  latticeArea      computes the lattice area of a polygon
     56  picksFormula     computes the ingrediants of Pick's formula for a polygon
     57  ellipticNF       computes the normal form of an elliptic polygon
     58  ellipticNFDB     displays the 16 normal forms of elliptic polygons
    5659
    5760AUXILARY PROCEDURES:
    58      polymakeKeepTmpFiles(int)     determines whether the files created in /tmp should be kept
     61  polymakeKeepTmpFiles  determines if the files created in /tmp should be kept
    5962
    6063KEYWORDS:    polytope; fan; secondary fan; secondary polytope; polymake;
    61              Newton polytope; Groebner fan
    62 
     64             Newton polytope; Groebner fan
    6365";
    6466
    65 ////////////////////////////////////////////////////////////////////////////////////
     67////////////////////////////////////////////////////////////////////////////////
    6668/// Auxilary Static Procedures in this Library
    67 ////////////////////////////////////////////////////////////////////////////////////
     69////////////////////////////////////////////////////////////////////////////////
    6870/// - scalarproduct
    6971/// - intmatcoldelete
    … …  
    7880/// - sortintvec
    7981/// - matrixtointmat
    80 /////////////////////////////////////////////////////////////////////////////////////
    81 
    82 ////////////////////////////////////////////////////////////////////////////////////
     82////////////////////////////////////////////////////////////////////////////////
     83
     84////////////////////////////////////////////////////////////////////////////////
    8385LIB "poly.lib";
    8486LIB "linalg.lib";
    8587LIB "random.lib";
    86 ////////////////////////////////////////////////////////////////////////////////////
    87 
    88 
    89 ////////////////////////////////////////////////////////////////////////////////////////
     88////////////////////////////////////////////////////////////////////////////////
     89
     90
     91/////////////////////////////////////////////////////////////////////////////
    9092/// PROCEDURES USING POLYMAKE
    91 ////////////////////////////////////////////////////////////////////////////////////////
     93/////////////////////////////////////////////////////////////////////////////
    9294
    9395proc polymakePolytope (intmat polytope,list #)
    9496"USAGE:  polymakePolytope(polytope[,#]);   polytope list, # string
    95 ASSUME:  each row of polytope gives the coordinates of a lattice point of a polytope
    96          with their affine coordinates as given by the output of secondaryPolytope
    97 PURPOSE: the procedure calls polymake to compute the vertices of the polytope as well
    98          as its dimension and information on its facets
     97ASSUME:  each row of polytope gives the coordinates of a lattice point of a
     98         polytope with their affine coordinates as given by the output of
     99         secondaryPolytope
     100PURPOSE: the procedure calls polymake to compute the vertices of the polytope
     101         as well as its dimension and information on its facets
    99102RETURN:  list, L with four entries
    100103@*            L[1] : an integer matrix whose rows are the coordinates of vertices
    101                      of the polytope
     104                     of the polytope 
    102105@*            L[2] : the dimension of the polytope
    103 @*            L[3] : a list whose ith entry explains to which vertices the ith vertex
    104                      of the Newton polytope is connected -- i.e. L[3][i] is an integer
    105                      vector and an entry k in there means that the vertex L[1][i] is
    106                      connected to the vertex L[1][k]
    107 @*            L[4] : an integer matrix whose rows mulitplied by (1,var(1),...,var(nvar)) give
    108                      a linear system of equations describing the affine hull of the polytope,
     106@*            L[3] : a list whose ith entry explains to which vertices the
     107                     ith vertex of the Newton polytope is connected
     108                     -- i.e. L[3][i] is an integer vector and an entry k in
     109                        there means that the vertex L[1][i] is connected to the
     110                        vertex L[1][k]
     111@*            L[4] : an integer matrix whose rows mulitplied by
     112                     (1,var(1),...,var(nvar)) give a linear system of equations
     113                     describing the affine hull of the polytope,
    109114                     i.e. the smallest affine space containing the polytope
    110 NOTE: -  for its computations the procedure calls the program polymake by Ewgenij Gawrilow,
    111          TU Berlin and Michael Joswig, TU Darmstadt; it therefore is necessary that
    112          this program is installed in order to use this procedure;
     115NOTE: -  for its computations the procedure calls the program polymake by
     116         Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt;
     117         it therefore is necessary that this program is installed in order
     118         to use this procedure;
    113119         see http://www.math.tu-berlin.de/polymake/
    114 @*    -  note that in the vertex edge graph we have changed the polymake convention which
    115          starts indexing its vertices by zero while we start with one !
    116 @*    -  the procedure creates the file  /tmp/polytope.polymake which contains the polytope
    117          in polymake format; if you wish to use this for further computations with polymake,
    118          you have to use the procedure polymakeKeepTmpFiles in before
    119 @*    -  moreover, the procedure creates the file /tmp/polytope.output which it deletes
    120          again before ending
    121 @*    -  it is possible to give as an optional second argument as string which then will be
    122          used instead of 'polytope' in the name of the polymake output file
     120@*    -  note that in the vertex edge graph we have changed the polymake
     121         convention which starts indexing its vertices by zero while we start
     122         with one !
     123@*    -  the procedure creates the file  /tmp/polytope.polymake which contains
     124         the polytope in polymake format; if you wish to use this for further
     125         computations with polymake, you have to use the procedure
     126         polymakeKeepTmpFiles in before
     127@*    -  moreover, the procedure creates the file /tmp/polytope.output which
     128         it deletes again before ending
     129@*    -  it is possible to give as an optional second argument as string
     130         which then will be used instead of 'polytope' in the name of the
     131         polymake output file
    123132EXAMPLE: example polymakePolytope;   shows an example"
    124133{
    … …  
    191200      }
    192201    }
    193   }
     202  } 
    194203  newveg=newveg[1,size(newveg)-1];
    195204  execute("list nveg="+newveg+";");
    … …  
    226235   "EXAMPLE:";
    227236   echo=2;
    228    // the lattice points of the unit square in the plane
     237   // the lattice points of the unit square in the plane 
    229238   list points=intvec(0,0),intvec(0,1),intvec(1,0),intvec(1,1);
    230239   // the secondary polytope of this lattice point configuration is computed
    … …  
    244253}
    245254
     255/////////////////////////////////////////////////////////////////////////////
     256
    246257proc newtonPolytope (poly f,list #)
    247258"USAGE: newtonPolytope(f[,#]);  f poly, # string
    … …  
    250261                     of the Newton polytope of f
    251262@*            L[2] : the dimension of the Newton polytope of f
    252 @*            L[3] : a list whose ith entry explains to which vertices the ith vertex
    253                      of the Newton polytope is connected -- i.e. L[3][i] is an integer
    254                      vector and an entry k in there means that the vertex L[1][i] is
    255                      connected to the vertex L[1][k]
    256 @*            L[4] : an integer matrix whose rows mulitplied by (1,var(1),...,var(nvar)) give
    257                      a linear system of equations describing the affine hull of the Newton
    258                      polytope, i.e. the smallest affine space containing the Newton polytope
    259 NOTE: -  if we replace the first column of L[4] by zeros, i.e. if we move the affine hull to
    260          the origin, then we get the equations for the orthogonal comploment of the linearity
    261          space of the normal fan dual to the Newton polytope, i.e. we get the EQUATIONS that
     263@*            L[3] : a list whose ith entry explains to which vertices the
     264                     ith vertex of the Newton polytope is connected
     265                     -- i.e. L[3][i] is an integer vector and an entry k in
     266                        there means that the vertex L[1][i] is
     267                        connected to the vertex L[1][k]
     268@*            L[4] : an integer matrix whose rows mulitplied by
     269                     (1,var(1),...,var(nvar)) give a linear system of equations
     270                     describing the affine hull of the Newton polytope, i.e. the
     271                     smallest affine space containing the Newton polytope
     272NOTE: -  if we replace the first column of L[4] by zeros, i.e. if we move
     273         the affine hull to the origin, then we get the equations for the
     274         orthogonal comploment of the linearity space of the normal fan dual
     275         to the Newton polytope, i.e. we get the EQUATIONS that
    262276         we need as input for polymake when computing the normal fan
    263277@*    -  the procedure calls for its computation polymake by Ewgenij Gawrilow,
    264278         TU Berlin and Michael Joswig, so it only works if polymake is installed;
    265279         see http://www.math.tu-berlin.de/polymake/
    266 @*    -  the procedure creates the file  /tmp/newtonPolytope.polymake which contains the polytope
    267          in polymake format and which can be used for further computations with polymake
    268 @*    -  moreover, the procedure creates the file /tmp/newtonPolytope.output which it deletes
    269          again before ending
    270 @*    -  it is possible to give as an optional second argument as string which then will be
    271          used instead of 'newtonPolytope' in the name of the polymake output file
     280@*    -  the procedure creates the file  /tmp/newtonPolytope.polymake which
     281         contains the polytope in polymake format and which can be used for
     282         further computations with polymake
     283@*    -  moreover, the procedure creates the file /tmp/newtonPolytope.output
     284         which it deletes again before ending
     285@*    -  it is possible to give as an optional second argument as string
     286         which then will be used instead of 'newtonPolytope' in the name of
     287         the polymake output file
    272288EXAMPLE: example newtonPolytope;   shows an example"
    273289{
    274290  int i,j;
    275   // compute the list of exponent vectors of the polynomial, which are the lattice points
     291  // compute the list of exponent vectors of the polynomial,
     292  // which are the lattice points
    276293  // whose convex hull is the Newton polytope of f
    277294  intmat exponents[size(f)][nvars(basering)];
    … …  
    303320   np[2];
    304321   // np[3] contains information how the vertices are connected to each other,
    305    // e.g. the first vertex (number 0) is connected to the second, third and
     322   // e.g. the first vertex (number 0) is connected to the second, third and 
    306323   //      fourth vertex
    307324   np[3][1];
    … …  
    313330   np[1];
    314331   // its dimension is
    315    np[2];
    316    // the Newton polytope is contained in the affine space given
     332   np[2];   
     333   // the Newton polytope is contained in the affine space given 
    317334   //     by the equations
    318335   np[4]*M;
    319336}
    320337
     338/////////////////////////////////////////////////////////////////////////////
     339
    321340proc newtonPolytopeLP (poly f)
    322341"USAGE:  newtonPolytopeLP(f);  f poly
    323 RETURN: list, the exponent vectors of the monomials occuring in f, i.e. the lattice
    324               points of the Newton polytope of f
     342RETURN: list, the exponent vectors of the monomials occuring in f,
     343              i.e. the lattice points of the Newton polytope of f
    325344EXAMPLE: example normalFan;   shows an example"
    326345{
    … …  
    345364}
    346365
     366/////////////////////////////////////////////////////////////////////////////
     367
    347368proc normalFan (intmat vertices,intmat affinehull,list graph,int er,list #)
    348369"USAGE:  normalFan (vert,aff,graph,rays,[,#]);   vert,aff intmat,  graph list, rays int, # string
    349 ASSUME:  - vert is an integer matrix whose rows are the coordinate of the vertices of
    350            a convex lattice polytope;
     370ASSUME:  - vert is an integer matrix whose rows are the coordinate of
     371           the vertices of a convex lattice polytope;
    351372@*       - aff describes the affine hull of this polytope, i.e.
    352            the smallest affine space containing it, in the following sense:
    353            denote by n the number of columns of vert, then multiply aff by (1,x(1),...,x(n))
    354            and set the resulting terms to zero in order to get the equations for the affine hull;
    355 @*       - the ith entry of graph is an integer vector describing to which vertices
    356            the ith vertex is connected, i.e. a k as entry means that the vertex vert[i] is
    357            connected to vert[k];
    358 @*       - the integer rays is either one (if the extreme rays should be computed) or zero (otherwise)
    359 RETURN:  list, the ith entry of L[1] contains information about the cone in the normal fan
    360                dual to the ith vertex of the polytope
    361 @*             L[1][i][1] = integer matrix representing the inequalities which describe the
    362                             cone dual to the ith vertex
    363 @*             L[1][i][2] = a list which contains the inequalities represented by L[i][1]
    364                             as a list of strings, where we use the variables x(1),...,x(n)
    365 @*             L[1][i][3] = only present if 'er' is set to 1; in that case it is an interger matrix
    366                             whose rows are the extreme rays of the cone
    367 @*             L[2] = is an integer matrix whose rows span the linearity space of the fan,
    368                       i.e. the linear space which is contained in each cone
     373           the smallest affine space containing it, in the following sense:
     374           denote by n the number of columns of vert, then multiply aff by
     375           (1,x(1),...,x(n)) and set the resulting terms to zero in order to
     376           get the equations for the affine hull;
     377@*       - the ith entry of graph is an integer vector describing to which
     378           vertices the ith vertex is connected, i.e. a k as entry means that
     379           the vertex vert[i] is connected to vert[k];
     380@*       - the integer rays is either one (if the extreme rays should be
     381           computed) or zero (otherwise)
     382RETURN:  list, the ith entry of L[1] contains information about the cone in the
     383               normal fan dual to the ith vertex of the polytope
     384@*             L[1][i][1] = integer matrix representing the inequalities which
     385                            describe the cone dual to the ith vertex
     386@*             L[1][i][2] = a list which contains the inequalities represented
     387                            by L[i][1] as a list of strings, where we use the
     388                            variables x(1),...,x(n)
     389@*             L[1][i][3] = only present if 'er' is set to 1; in that case it is
     390                            an interger matrix whose rows are the extreme rays
     391                            of the cone
     392@*             L[2] = is an integer matrix whose rows span the linearity space
     393                      of the fan, i.e. the linear space which is contained in
     394                      each cone
    369395NOTE:    - the procedure calls for its computation polymake by Ewgenij Gawrilow,
    370            TU Berlin and Michael Joswig, so it only works if polymake is installed;
     396           TU Berlin and Michael Joswig, so it only works if polymake is
     397           installed;
    371398           see http://www.math.tu-berlin.de/polymake/
    372 @*       - in the optional argument # it is possible to hand over other names for the
    373            variables to be used -- be carful, the format must be correct and that is
    374            not tested, e.g. if you want the variable names to be u00,u10,u01,u11
    375            then you must hand over the string u11,u10,u01,u11
     399@*       - in the optional argument # it is possible to hand over other names
     400           for the variables to be used -- be carful, the format must be correct
     401           and that is not tested, e.g. if you want the variable names to be
     402           u00,u10,u01,u11 then you must hand over the string u11,u10,u01,u11
    376403EXAMPLE: example normalFan;   shows an example"
    377404{
    378405  list ineq; // stores the inequalities of the cones
    379406  int i,j,k;
    380   // we work over the following ring
     407  // we work over the following ring 
    381408  execute("ring ineqring=0,x(1.."+string(ncols(vertices))+"),lp;");
    382409  string greatersign=">";
    … …  
    403430  for (i=1;i<=nrows(vertices);i++)
    404431  {
    405     // first we produce for each vertex in the polytope
     432    // first we produce for each vertex in the polytope 
    406433    // the inequalities describing the dual cone in the normal fan
    407     list pp;  // contain strings representing the inequalities describing the normal cone
    408     intmat ie[size(graph[i])][ncols(vertices)]; // contains the inequalities as rows
    409     // consider all the vertices to which the ith vertex in the polytope is connected by an edge
     434    list pp;  // contain strings representing the inequalities
     435              // describing the normal cone
     436    intmat ie[size(graph[i])][ncols(vertices)]; // contains the inequalities
     437                                                // as rows
     438    // consider all the vertices to which the ith vertex in the
     439    // polytope is connected by an edge
    410440    for (j=1;j<=size(graph[i]);j++)
    411441    {
    412442      // produce the vector ie_j pointing from the jth vertex to the ith vertex;
    413       // this will be the jth inequality for the cone in the normal fan dual to the ith vertex
     443      // this will be the jth inequality for the cone in the normal fan dual to
     444      // the ith vertex
    414445      ie[j,1..ncols(vertices)]=vertices[i,1..ncols(vertices)]-vertices[graph[i][j],1..ncols(vertices)];
    415446      EXP=ie[j,1..ncols(vertices)];
    … …  
    417448      p=(VAR*EXP)[1,1];
    418449      pl,pr=0,0;
    419       // separate the terms with positive coefficients in p from those with negative coefficients
     450      // separate the terms with positive coefficients in p from
     451      // those with negative coefficients
    420452      for (k=1;k<=size(p);k++)
    421453      {
    … …  
    429461        }
    430462      }
    431       // build the string which represents the jth inequality for the cone dual to the ith vertex
    432       // as polynomial inequality of type string, and store this in the list pp as jth entry
     463      // build the string which represents the jth inequality
     464      // for the cone dual to the ith vertex
     465      // as polynomial inequality of type string, and store this
     466      // in the list pp as jth entry
    433467      pp[j]=string(pl)+" "+greatersign+" "+string(pr);
    434468    }
    … …  
    462496    // create the file ineq.output
    463497    write(":w /tmp/ineq.output","");
    464     int dimension; // keeps the dimension of the intersection the bad cones with the u11tobeseencone
     498    int dimension; // keeps the dimension of the intersection the
     499                   // bad cones with the u11tobeseencone
    465500    for (i=1;i<=size(ineq);i++)
    466501    {
    467       i,". Cone of ",nrows(vertices); // indicate how many vertices have been dealt with
     502      i,". Cone of ",nrows(vertices); // indicate how many
     503                                      // vertices have been dealt with
    468504      ungleichungen=intmatToPolymake(ineq[i][1],"rays");
    469505      // write the inequalities to ineq.polymake and call polymake
    … …  
    489525  }
    490526  // get the linearity space
    491   return(list(ineq,linearity));
     527  return(list(ineq,linearity)); 
    492528}
    493529example
    … …  
    514550}
    515551
     552/////////////////////////////////////////////////////////////////////////////
     553
    516554proc groebnerFan (poly f,list #)
    517555"USAGE:  groebnerFan(f[,#]);  f poly, # string
    518 RETURN:  list, the ith entry of L[1] contains information about the ith cone in the Groebner fan
    519                dual to the ith vertex in the Newton polytope of the f
    520 @*             L[1][i][1] = integer matrix representing the inequalities which describe the cone
    521 @*             L[1][i][2] = a list which contains the inequalities represented by L[1][i][1]
    522                             as a list of strings
    523 @*             L[1][i][3] = an interger matrix whose rows are the extreme rays of the cone
    524 @*             L[2] = is an integer matrix whose rows span the linearity space of the fan,
    525                       i.e. the linear space which is contained in each cone
    526 @*             L[3] = the Newton polytope of f in the format of the procedure newtonPolytope
    527 @*             L[4] = integer matrix where each row represents the exponet vector of one monomial
    528                       occuring in the input polynomial
    529 NOTE:    - if you have alread computed the Newton polytope of f then you might want
    530            to use the procedure normalFan instead in order to avoid doing costly computation
    531            twice
    532 @*       - the procedure calls for its computation polymake by Ewgenij Gawrilow,
    533            TU Berlin and Michael Joswig, so it only works if polymake is installed;
    534            see http://www.math.tu-berlin.de/polymake/
    535 @*       - the procedure creates the file  /tmp/newtonPolytope.polymake which contains the
    536            Newton polytope of f in polymake format and which can be used for further
    537            computations with polymake
    538 @*       - it is possible to give as an optional second argument as string which then will be
    539            used instead of 'newtonPolytope' in the name of the polymake output file
     556RETURN:  list, the ith entry of L[1] contains information about the ith cone
     557               in the Groebner fan dual to the ith vertex in the Newton
     558               polytope of the f
     559@*             L[1][i][1] = integer matrix representing the inequalities
     560                            which describe the cone         
     561@*             L[1][i][2] = a list which contains the inequalities represented
     562                            by L[1][i][1] as a list of strings
     563@*             L[1][i][3] = an interger matrix whose rows are the extreme rays
     564                            of the cone
     565@*             L[2] = is an integer matrix whose rows span the linearity space
     566                      of the fan, i.e. the linear space which is contained
     567                      in each cone               
     568@*             L[3] = the Newton polytope of f in the format of the procedure
     569                      newtonPolytope
     570@*             L[4] = integer matrix where each row represents the exponet
     571                      vector of one monomial occuring in the input polynomial
     572NOTE: - if you have alread computed the Newton polytope of f then you might want
     573        to use the procedure normalFan instead in order to avoid doing costly
     574        computation twice
     575@*    - the procedure calls for its computation polymake by Ewgenij Gawrilow,
     576        TU Berlin and Michael Joswig, so it only works if polymake is installed;
     577        see http://www.math.tu-berlin.de/polymake/
     578@*    - the procedure creates the file  /tmp/newtonPolytope.polymake which
     579        contains the Newton polytope of f in polymake format and which can
     580        be used for further computations with polymake
     581@*    - it is possible to give as an optional second argument as string which
     582        then will be used instead of 'newtonPolytope' in the name of the
     583        polymake output file
    540584EXAMPLE: example groebnerFan;   shows an example"
    541585{
    542586  int i,j;
    543   // compute the list of exponent vectors of the polynomial, which are the lattice points
    544   // whose convex hull is the Newton polytope of f
     587  // compute the list of exponent vectors of the polynomial, which are
     588  // the lattice points whose convex hull is the Newton polytope of f
    545589  intmat exponents[size(f)][nvars(basering)];
    546590  while (f!=0)
    … …  
    601645
    602646
     647/////////////////////////////////////////////////////////////////////////////
     648
    603649proc intmatToPolymake (intmat M,string art)
    604650"USAGE:  intmatToPolymake(M,art);  M intmat, art string
    605 ASSUME:  - M is an integer matrix which should be transformed into polymake format;
     651ASSUME:  - M is an integer matrix which should be transformed into polymake
     652           format;
    606653@*       - art is one of the following strings:
    607 @*         + 'rays'   : indicating that a first column of 0's should be added
    608 @*         + 'points' : indicating that a first column of 1's should be added
    609 RETURN:  string, the matrix is transformed in a string and a first column has been added
     654@*         + 'rays'   : indicating that a first column of 0's should be added
     655@*         + 'points' : indicating that a first column of 1's should be added
     656RETURN:  string, the matrix is transformed in a string and a first column has
     657                 been added
    610658EXAMPLE: example intmatToPolymake;   shows an example"
    611659{
    … …  
    614662    string anf="0 ";
    615663  }
    616   else
     664  else 
    617665  {
    618666    string anf="1 ";
    … …  
    645693}
    646694
     695/////////////////////////////////////////////////////////////////////////////
     696
    647697proc polymakeToIntmat (string pm,string art)
    648698"USAGE:  polymakeToIntmat(pm,art);  pm, art string
    649 ASSUME:  pm is the result of calling polymake with one 'argument' like VERTICES, AFFINE_HULL, etc.,
    650          so that the first row of the string is the name of the corresponding 'argument' and
    651          the further rows contain the result which consists of vectors either over the integers
     699ASSUME:  pm is the result of calling polymake with one 'argument' like
     700         VERTICES, AFFINE_HULL, etc., so that the first row of the string is
     701         the name of the corresponding 'argument' and the further rows contain
     702         the result which consists of vectors either over the integers
    652703         or over the rationals
    653 RETURN:  intmat, the rows of the matrix are basically the vectors in pm from the second row on
    654                  where each row has been multiplied with the lowest common multiple of the
    655                  denominators of its entries so as to be an integer matrix; moreover,
    656                  if art=='affine', then the first column is omitted since we only want affine
     704RETURN:  intmat, the rows of the matrix are basically the vectors in pm from
     705                 the second row on where each row has been multiplied with the
     706                 lowest common multiple of the denominators of its entries so
     707                 as to be an integer matrix; moreover, if art=='affine', then
     708                 the first column is omitted since we only want affine
    657709                 coordinates
    658710EXAMPLE: example polymakeToIntmat;   shows an example"
    … …  
    666718    pm=stringdelete(pm,1);
    667719  }
    668   pm=stringdelete(pm,1);
    669   // find out how many entries each vector has, namely one more than 'spaces' in a row
     720  pm=stringdelete(pm,1); 
     721  // find out how many entries each vector has, namely one more
     722  // than 'spaces' in a row
    670723  int i=1;
    671724  int s=1;
    … …  
    681734  // if we want to have affine coordinates
    682735  if (art=="affine")
    683   {
     736  {   
    684737    s--; // then there is one column less
    685738    // and the entry of the first column (in the first row) has to be removed
    … …  
    690743    pm=stringdelete(pm,1);
    691744  }
    692   // we add two line breaks at the end in order to have this as a stopping criterion
     745  // we add two line breaks at the end in order to have this as
     746  // a stopping criterion
    693747  pm=pm+zeilenumbruch+zeilenumbruch;
    694748  // we now have to work through each row
    … …  
    707761        z++;
    708762        pm[i]=",";
    709         // if we want to have affine coordinates, then we have to delete the first entry in each row
     763        // if we want to have affine coordinates,
     764        // then we have to delete the first entry in each row
    710765        if (art=="affine")
    711766        {
    … …  
    720775      if (pm[i]==" ")
    721776      {
    722         pm[i]=",";
     777        pm[i]=",";     
    723778      }
    724779    }
    … …  
    729784    pm=stringdelete(pm,size(pm));
    730785  }
    731   // since the matrix could be over the rationals, we need a ring with rational coefficients
    732   ring zwischering=0,x,lp;
     786  // since the matrix could be over the rationals,
     787  // we need a ring with rational coefficients
     788  ring zwischering=0,x,lp;   
    733789  // create the matrix with the elements of pm as entries
    734790  execute("matrix mm["+string(z)+"]["+string(s)+"]="+pm+";");
    … …  
    773829}
    774830
    775 ////////////////////////////////////////////////////////////////////////////////////////
     831///////////////////////////////////////////////////////////////////////////////
    776832/// PROCEDURES USING TOPCOM
    777 ////////////////////////////////////////////////////////////////////////////////////////
     833///////////////////////////////////////////////////////////////////////////////
    778834
    779835proc triangulations (list polygon)
    780836"USAGE:  triangulations(polygon); list polygon
    781 ASSUME:  polygon is a list of integer vectors of the same size representing the affine
    782          coordinates of the lattice points
     837ASSUME:  polygon is a list of integer vectors of the same size representing
     838         the affine coordinates of the lattice points
    783839PURPOSE: the procedure considers the marked polytope given as the convex hull of
    784840         the lattice points and with these lattice points as markings; it then
    785          computes all possible triangulations of this marked polytope
     841         computes all possible triangulations of this marked polytope 
    786842RETURN:  list, each entry corresponds to one triangulation and the ith entry is
    787843               itself a list of integer vectors of size three, where each integer
    788844               vector defines one triangle in the triangulation by telling which
    789845               points of the input are the vertices of the triangle
    790 NOTE:  - the procedure calls for its computations the program points2triangs
    791          from the program topcom by Joerg Rambau, Universitaet Bayreuth; it
    792          therefore is necessary that this program is installed in order to use this
    793          procedure; see
    794 @*       http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM
    795 @*     - the procedure creates the files /tmp/triangulationsinput and /tmp/triangulationsoutput;
    796          the former is used as input for points2triangs and the latter is its output
    797          containing the triangulations of corresponding to points in the format
    798          of points2triangs; if you wish to use this for further computations with topcom,
    799          you have to use the procedure polymakeKeepTmpFiles in before
    800 @*     - note that an integer i in an integer vector representing a triangle refers to
    801          the ith lattice point, i.e. polygon[i]; this convention is different from
    802          TOPCOM's convention, where i would refer to the i-1st lattice point
     846NOTE:- the procedure calls for its computations the program points2triangs
     847       from the program topcom by Joerg Rambau, Universitaet Bayreuth; it
     848       therefore is necessary that this program is installed in order to use
     849       this  procedure; see
     850@*     http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM
     851@*   - the procedure creates the files /tmp/triangulationsinput and
     852       /tmp/triangulationsoutput;
     853       the former is used as input for points2triangs and the latter is its
     854       output containing the triangulations of corresponding to points in the
     855       format of points2triangs; if you wish to use this for further
     856       computations with topcom, you have to use the procedure
     857       polymakeKeepTmpFiles in before
     858@*   - note that an integer i in an integer vector representing a triangle
     859       refers to the ith lattice point, i.e. polygon[i]; this convention is
     860       different from TOPCOM's convention, where i would refer to the i-1st
     861       lattice point
    803862EXAMPLE: example triangulations;   shows an example"
    804863{
    805864  int i,j;
    806   // prepare the input for points2triangs by writing the input polygon in the
     865  // prepare the input for points2triangs by writing the input polygon in the 
    807866  // necessary format
    808867  string spi="[";
    … …  
    820879  // call points2triangs
    821880  system("sh","cd /tmp; points2triangs < triangulationsinput > triangulationsoutput");
    822   string p2t=read("/tmp/triangulationsoutput"); // takes the result of points2triangs
     881  string p2t=read("/tmp/triangulationsoutput"); // takes result of points2triangs
    823882  // delete the tmp-files, if polymakekeeptmpfiles is not set
    824883  if (defined(polymakekeeptmpfiles)==0)
    … …  
    826885    system("sh","cd /tmp; rm -f triangulationsinput; rm -f triangulationsoutput");
    827886  }
    828   // preprocessing of p2t if points2triangs is version >= 0.15 brings p2t to the format of version 0.14
     887  // preprocessing of p2t if points2triangs is version >= 0.15
     888  // brings p2t to the format of version 0.14
    829889  string np2t; // takes the triangulations in Singular format
    830890  for (i=1;i<=size(p2t)-2;i++)
    … …  
    847907      }
    848908      else
    849       {
     909      {       
    850910        np2t=np2t+p2t[i];
    851911      }
    … …  
    859919  {
    860920    if (np2t[size(np2t)]!=";")
    861     {
     921    {     
    862922      np2t=np2t+p2t[size(p2t)-1]+p2t[size(p2t)];
    863923    }
    … …  
    881941          np2t=np2t+"))";
    882942          i++;
    883         }
     943        }     
    884944        else
    885945        {
    … …  
    919979   "EXAMPLE:";
    920980   echo=2;
    921    // the lattice points of the unit square in the plane
     981   // the lattice points of the unit square in the plane 
    922982   list polygon=intvec(0,0),intvec(0,1),intvec(1,0),intvec(1,1);
    923983   // the triangulations of this lattice point configuration are computed
    … …  
    926986}
    927987
     988/////////////////////////////////////////////////////////////////////////////
     989
    928990proc secondaryPolytope (list polygon,list #)
    929991"USAGE:  secondaryPolytope(polygon[,#]); list polygon, list #
    930 ASSUME:  - polygon is a list of integer vectors of the same size representing the affine
    931            coordinates of lattice points
    932 @*       - if the triangulations of the corresponding polygon have already been computed
    933            with the procedure triangulations then these can be given as a second (optional)
    934            argument in order to avoid doing this computation again
     992ASSUME:  - polygon is a list of integer vectors of the same size representing
     993           the affine coordinates of lattice points
     994@*       - if the triangulations of the corresponding polygon have already been
     995           computed with the procedure triangulations then these can be given as
     996           a second (optional) argument in order to avoid doing this computation
     997           again
    935998PURPOSE: the procedure considers the marked polytope given as the convex hull of
    936999         the lattice points and with these lattice points as markings; it then
    937          computes the lattice points of the secondary polytope given by this
     1000         computes the lattice points of the secondary polytope given by this 
    9381001         marked polytope which correspond to the triangulations computed by
    9391002         the procedure triangulations
    9401003RETURN:  list, say L, such that:
    941 @*             L[1] = intmat, each row gives the affine coordinates of a lattice point
    942                       in the secondary polytope given by the marked
     1004@*             L[1] = intmat, each row gives the affine coordinates of a lattice
     1005                      point in the secondary polytope given by the marked
    9431006                      polytope corresponding to polygon
    9441007@*             L[2] = the list of corresponding triangulations
    945 NOTE:    if the triangluations are not handed over as optional argument the procedure calls
    946          for its computation of these triangulations the program points2triangs
    947          from the program topcom by Joerg Rambau, Universitaet Bayreuth; it
    948          therefore is necessary that this program is installed in order to use this
    949         procedure; see
    950 @*       http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM
     1008NOTE: if the triangluations are not handed over as optional argument the
     1009      procedure calls for its computation of these triangulations the program
     1010      points2triangs from the program topcom by Joerg Rambau, Universitaet
     1011      Bayreuth; it therefore is necessary that this program is installed in
     1012      order to use this procedure; see
     1013@*    http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM
    9511014EXAMPLE: example secondaryPolytope;   shows an example"
    9521015{
    … …  
    9621025  int i,j,k,l;
    9631026  intmat N[2][2]; // is used to compute areas of triangles
    964   intvec vertex;  // stores a point in the secondary polytope as intermediate result
     1027  intvec vertex;  // stores a point in the secondary polytope as
     1028                  // intermediate result
    9651029  int eintrag;
    9661030  int halt;
    967   intmat secpoly[size(triangs)][size(polygon)];   // stores all lattice points of the secondary polytope
    968   // consider each triangulation and compute the corresponding point in the secondary polytope
     1031  intmat secpoly[size(triangs)][size(polygon)];   // stores all lattice points
     1032                                                  // of the secondary polytope
     1033  // consider each triangulation and compute the corresponding point
     1034  // in the secondary polytope
    9691035  for (i=1;i<=size(triangs);i++)
    9701036  {
    971     // for each triangulation we have to compute the coordinates corresponding to each marked point
     1037    // for each triangulation we have to compute the coordinates
     1038    // corresponding to each marked point
    9721039    for (j=1;j<=size(polygon);j++)
    9731040    {
    9741041      eintrag=0;
    975       // for each marked point we have to consider all triangles in the triangulation
    976       // which involve this particular point
     1042      // for each marked point we have to consider all triangles in the
     1043      // triangulation which involve this particular point
    9771044      for (k=1;k<=size(triangs[i]);k++)
    9781045      {
    … …  
    9951062    secpoly[i,1..size(polygon)]=vertex;
    9961063  }
    997   return(list(secpoly,triangs));
     1064  return(list(secpoly,triangs));         
    9981065}
    9991066example
    … …  
    10111078}
    10121079
    1013 ////////////////////////////////////////////////////////////////////////////////////////
     1080///////////////////////////////////////////////////////////////////////////////
    10141081/// PROCEDURES USING POLYMAKE AND TOPCOM
    1015 ////////////////////////////////////////////////////////////////////////////////////////
     1082///////////////////////////////////////////////////////////////////////////////
    10161083
    10171084proc secondaryFan (list polygon,list #)
    10181085"USAGE:  secondaryFan(polygon[,#]); list polygon, list #
    1019 ASSUME:  - polygon is a list of integer vectors of the same size representing the affine
    1020            coordinates of lattice points
    1021 @*       - if the triangulations of the corresponding polygon have already been computed
    1022            with the procedure triangulations then these can be given as a second (optional)
    1023            argument in order to avoid doing this computation again
     1086ASSUME:  - polygon is a list of integer vectors of the same size representing
     1087           the affine coordinates of lattice points
     1088@*       - if the triangulations of the corresponding polygon have already been
     1089           computed with the procedure triangulations then these can be given
     1090           as a second (optional) argument in order to avoid doing this
     1091           computation again
    10241092PURPOSE: the procedure considers the marked polytope given as the convex hull of
    10251093         the lattice points and with these lattice points as markings; it then
    1026          computes the lattice points of the secondary polytope given by this
     1094         computes the lattice points of the secondary polytope given by this 
    10271095         marked polytope which correspond to the triangulations computed by
    10281096         the procedure triangulations
    1029 RETURN:  list, the ith entry of L[1] contains information about the ith cone in the
    1030                secondary fan of the polygon, i.e. the cone dual to the ith vertex of the
    1031                secondary polytope
    1032 @*             L[1][i][1] = integer matrix representing the inequalities which describe the
    1033                             cone dual to the ith vertex
    1034 @*             L[1][i][2] = a list which contains the inequalities represented by L[1][i][1]
    1035                             as a list of strings, where we use the variables x(1),...,x(n)
    1036 @*             L[1][i][3] = only present if 'er' is set to 1; in that case it is an interger matrix
    1037                             whose rows are the extreme rays of the cone
    1038 @*             L[2] = is an integer matrix whose rows span the linearity space of the fan,
    1039                       i.e. the linear space which is contained in each cone
    1040 @*             L[3] = the secondary polytope in the format of the procedure polymakePolytope
    1041 @*             L[4] = the list of triangulations corresponding to the vertices
     1097RETURN:  list, the ith entry of L[1] contains information about the ith cone in
     1098               the secondary fan of the polygon, i.e. the cone dual to the
     1099               ith vertex of the secondary polytope
     1100@*             L[1][i][1] = integer matrix representing the inequalities which
     1101                            describe the cone dual to the ith vertex
     1102@*             L[1][i][2] = a list which contains the inequalities represented
     1103                            by L[1][i][1] as a list of strings, where we use the
     1104                            variables x(1),...,x(n)
     1105@*             L[1][i][3] = only present if 'er' is set to 1; in that case it is
     1106                            an interger matrix whose rows are the extreme rays
     1107                            of the cone
     1108@*             L[2] = is an integer matrix whose rows span the linearity space
     1109                      of the fan, i.e. the linear space which is contained in
     1110                      each cone
     1111@*             L[3] = the secondary polytope in the format of the procedure
     1112                      polymakePolytope
     1113@*             L[4] = the list of triangulations corresponding to the vertices
    10421114                      of the secondary polytope
    1043 NOTE:    - the procedure calls for its computation polymake by Ewgenij Gawrilow,
    1044            TU Berlin and Michael Joswig, so it only works if polymake is installed;
    1045            see http://www.math.tu-berlin.de/polymake/
    1046 @*       - in the optional argument # it is possible to hand over other names for the
    1047            variables to be used -- be carful, the format must be correct and that is
    1048            not tested, e.g. if you want the variable names to be u00,u10,u01,u11
    1049            then you must hand over the string u11,u10,u01,u11
    1050 @*       - if the triangluations are not handed over as optional argument the procedure calls
    1051            for its computation of these triangulations the program points2triangs
    1052            from the program topcom by Joerg Rambau, Universitaet Bayreuth; it
    1053            therefore is necessary that this program is installed in order to use this
    1054            procedure; see
    1055 @*         http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM
     1115NOTE:- the procedure calls for its computation polymake by Ewgenij Gawrilow,
     1116       TU Berlin and Michael Joswig, so it only works if polymake is installed;
     1117       see http://www.math.tu-berlin.de/polymake/
     1118@*   - in the optional argument # it is possible to hand over other names for
     1119       the variables to be used -- be carful, the format must be correct and
     1120       that is not tested, e.g. if you want the variable names to be
     1121       u00,u10,u01,u11 then you must hand over the string u11,u10,u01,u11
     1122@*   - if the triangluations are not handed over as optional argument the
     1123       procedure calls for its computation of these triangulations the program
     1124       points2triangs from the program topcom by Joerg Rambau, Universitaet
     1125       Bayreuth; it therefore is necessary that this program is installed in
     1126       order to use this procedure; see
     1127@*     http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM
    10561128EXAMPLE: example secondaryFan;   shows an example"
    10571129{
    … …  
    10941166
    10951167
    1096 ////////////////////////////////////////////////////////////////////////////////////////
     1168////////////////////////////////////////////////////////////////////////////////
    10971169/// PROCEDURES CONCERNED WITH PLANAR POLYGONS
    1098 ////////////////////////////////////////////////////////////////////////////////////////
     1170////////////////////////////////////////////////////////////////////////////////
    10991171
    11001172proc cycleLength (list boundary,intvec interior)
    11011173"USAGE:  cycleLength(boundary,interior); list boundary, intvec interior
    1102 ASSUME:  boundary is a list of integer vectors describing a cycle in some convex lattice
    1103          polygon around the lattice point interior ordered clock wise
    1104 RETURN:  string, the cycle length of the corresponding cycle in the dual tropical curve
     1174ASSUME:  boundary is a list of integer vectors describing a cycle in some
     1175         convex lattice polygon around the lattice point interior ordered
     1176         clock wise
     1177RETURN:  string, the cycle length of the corresponding cycle in the dual
     1178                 tropical curve
    11051179EXAMPLE: example cycleLength;   shows an example"
    11061180{
    11071181  int j;
    1108   // create a ring whose variables are indexed by the points in boundary resp. by interior
     1182  // create a ring whose variables are indexed by the points in
     1183  // boundary resp. by interior
    11091184  string rst="ring cyclering=0,(u"+string(interior[1])+string(interior[2]);
    11101185  for (j=1;j<=size(boundary);j++)
    … …  
    11211196  matrix N2[2][2]; // used to compute the area of a triangle
    11221197  matrix N3[2][2]; // used to compute the area of a triangle
    1123   // for each original point in the boundary compute its contribution to the cycle
     1198  // for each original point in boundary compute its contribution to the cycle
    11241199  for (j=2;j<=size(boundary)-1;j++)
    11251200  {
    … …  
    11431218   // interior is a lattice point in the interior of this lattice polygon
    11441219   intvec interior=1,1;
    1145    // compute the general cycle length of a cycle of the corresponding cycle
     1220   // compute the general cycle length of a cycle of the corresponding cycle 
    11461221   // in the dual tropical curve, note that (0,1) and (2,1) do not contribute
    11471222   cycleLength(boundary,interior);
    11481223}
    11491224
     1225/////////////////////////////////////////////////////////////////////////////
     1226
    11501227proc splitPolygon (list markings)
    11511228"USAGE:  splitPolygon (markings);  markings list
    1152 ASSUME:  markings is a list of integer vectors representing lattice points in the plane
    1153          which we consider as the marked points of the convex lattice polytope spanned by them
    1154 PURPOSE: split the marked points in the vertices, the points on the facets which are not vertices,
    1155          and the interior points
     1229ASSUME:  markings is a list of integer vectors representing lattice points in
     1230         the plane which we consider as the marked points of the convex lattice
     1231         polytope spanned by them
     1232PURPOSE: split the marked points in the vertices, the points on the facets
     1233         which are not vertices, and the interior points
    11561234RETURN:  list, L consisting of three lists
    11571235@*             L[1]    : represents the vertices the polygon ordered clockwise
    11581236@*                       L[1][i][1] = intvec, the coordinates of the ith vertex
    11591237@*                       L[1][i][2] = int, the position of L[1][i][1] in markings
    1160 @*             L[2][i] : represents the lattice points on the facet of the polygon with
    1161                          endpoints L[1][i] and L[1][i+1] (i considered modulo size(L[1]))
    1162 @*                       L[2][i][j][1] = intvec, the coordinates of the jth lattice point on that facet
    1163 @*                       L[2][i][j][2] = int, the position of L[2][i][j][1] in markings
    1164 @*             L[3]    : represents the interior lattice points of the polygon
    1165 @*                       L[3][i][1] = intvec, the coordinates of the ith interior point
     1238@*             L[2][i] : represents the lattice points on the facet of the
     1239                         polygon with endpoints L[1][i] and L[1][i+1]
     1240                         (i considered modulo size(L[1]))
     1241@*                       L[2][i][j][1] = intvec, the coordinates of the jth
     1242                                                 lattice point on that facet
     1243@*                       L[2][i][j][2] = int, the position of L[2][i][j][1]
     1244                                              in markings
     1245@*             L[3]    : represents the interior lattice points of the polygon
     1246@*                       L[3][i][1] = intvec, coordinates of ith interior point
    11661247@*                       L[3][i][2] = int, the position of L[3][i][1] in markings
    11671248EXAMPLE: example splitPolygon;   shows an example"
    … …  
    11731254  vert[1]=pb[2];
    11741255  int i,j,k;      // indices
    1175   list boundary;  // stores the points on the facets of the polygon which are not vertices
    1176   // append to the boundary points as well as to the vertices the first vertex a second time
     1256  list boundary;  // stores the points on the facets of the
     1257                  // polygon which are not vertices
     1258  // append to the boundary points as well as to the vertices
     1259  // the first vertex a second time
    11771260  pb[1]=pb[1]+list(pb[1][1]);
    11781261  pb[2]=pb[2]+list(pb[2][1]);
    … …  
    11981281  // store the information on the boundary in vert[2]
    11991282  vert[2]=boundary;
    1200   // find the remaining points in the input which are not on the boundary by checking
     1283  // find the remaining points in the input which are not on
     1284  // the boundary by checking
    12011285  // for each point in markings if it is contained in pb[1]
    12021286  list interior=markings;
    … …  
    12141298  // store the interior points in vert[3]
    12151299  vert[3]=interior;
    1216   // add to each point in vert the index which it gets from its position in the input markings;
     1300  // add to each point in vert the index which it gets from
     1301  // its position in the input markings;
    12171302  // do so for ver[1]
    12181303  for (i=1;i<=size(vert[1]);i++)
    … …  
    12471332    }
    12481333    vert[3][i]=list(vert[3][i],j);
    1249   }
     1334  } 
    12501335  return(vert);
    12511336}
    … …  
    12541339   "EXAMPLE:";
    12551340   echo=2;
    1256    // the lattice polygon spanned by the points (0,0), (3,0) and (0,3)
     1341   // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 
    12571342   // with all integer points as markings
    12581343   list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0),
    … …  
    12701355
    12711356
     1357/////////////////////////////////////////////////////////////////////////////
     1358
    12721359proc eta (list triang,list polygon)
    12731360"USAGE:  eta(triang,polygon);  triang, polygon list
    1274 ASSUME:  polygon has the format of the output of splitPolygon, i.e. it is a list with three
    1275          entries describing a convex lattice polygon in the following way:
    1276 @*       polygon[1] : is a list of lists; for each i the entry polygon[1][i][1] is a lattice point which is
    1277                       a vertex of the lattice polygon, and polygon[1][i][2] is an integer assigned to
     1361ASSUME:  polygon has the format of the output of splitPolygon, i.e. it is a
     1362         list with three entries describing a convex lattice polygon in the
     1363         following way:
     1364@*       polygon[1] : is a list of lists; for each i the entry polygon[1][i][1]
     1365                      is a lattice point which is a vertex of the lattice
     1366                      polygon, and polygon[1][i][2] is an integer assigned to
    12781367                      this lattice point as identifying index
    1279 @*       polygon[2] : is a list of lists; for each vertex of the polygon, i.e. for each entry in polygon[1],
    1280                       it contains a list polygon[2][i], which contains the lattice points on the facet
    1281                       with endpoints polygon[1][i] and polygon[1][i+1] - i considered mod size(polygon[1]);
    1282                       each such lattice point contributes an entry polygon[2][i][j][1] which is an integer
    1283                       vector giving the coordinate of the lattice point and an entry polygon[2][i][j][2]
    1284                       which is the identifying index
    1285 @*       polygon[3] : is a list of lists, where each entry corresponds to a lattice point in the
    1286                       interior of the polygon, with polygon[3][j][1] being the coordinates of the point
     1368@*       polygon[2] : is a list of lists; for each vertex of the polygon,
     1369                      i.e. for each entry in polygon[1], it contains a list
     1370                      polygon[2][i], which contains the lattice points on the
     1371                      facet with endpoints polygon[1][i] and polygon[1][i+1]
     1372                      - i considered mod size(polygon[1]);
     1373                      each such lattice point contributes an entry
     1374                      polygon[2][i][j][1] which is an integer
     1375                      vector giving the coordinate of the lattice point and an
     1376                      entry polygon[2][i][j][2] which is the identifying index
     1377@*       polygon[3] : is a list of lists, where each entry corresponds to a
     1378                      lattice point in the interior of the polygon, with
     1379                      polygon[3][j][1] being the coordinates of the point
    12871380                      and polygon[3][j][2] being the identifying index;
    1288 @*       triang is a list of integer vectors all of size three describing a triangulation of the
    1289          polygon described by polygon; if an entry of triang is the vector (i,j,k) then the triangle
    1290          is build by the vertices with indices i, j and k
    1291 RETURN:  intvec, the integer vector eta describing that vertex of the Newton polytope discriminant
    1292                  of the polygone whose dual cone in the Groebner fan contains the cone of the
    1293                  secondary fan of the polygon corresponding to the given triangulation
    1294 NOTE:    for a better description of eta see either Gelfand, Kapranov, Zelevinski: Discriminants,
    1295          Resultants and multidimensional Determinants. Chapter 10.
     1381@*       triang is a list of integer vectors all of size three describing a
     1382         triangulation of the polygon described by polygon; if an entry of
     1383         triang is the vector (i,j,k) then the triangle is build by the vertices
     1384         with indices i, j and k
     1385RETURN:  intvec, the integer vector eta describing that vertex of the Newton
     1386                 polytope discriminant of the polygone whose dual cone in the
     1387                 Groebner fan contains the cone of the secondary fan of the
     1388                 polygon corresponding to the given triangulation
     1389NOTE:  for a better description of eta see either Gelfand, Kapranov,
     1390       Zelevinski: Discriminants, Resultants and multidimensional Determinants.
     1391       Chapter 10.
    12961392EXAMPLE: example eta;   shows an example"
    12971393{
    12981394  int i,j,k,l,m,n; // index variables
    1299   list ordpolygon;   // stores the lattice points in the order used in the triangulation
     1395  list ordpolygon;   // stores the lattice points in the order
     1396                     // used in the triangulation
    13001397  list triangarea; // stores the areas of the triangulations
    13011398  intmat N[2][2];  // used to compute triangle areas
    … …  
    13221419  for (i=1;i<=size(triang);i++)
    13231420  {
    1324     // Note that the ith lattice point in orderedpolygon has the number i-1 in the triangulation!
     1421    // Note that the ith lattice point in orderedpolygon has the
     1422    // number i-1 in the triangulation!
    13251423    N=ordpolygon[triang[i][1]]-ordpolygon[triang[i][2]],ordpolygon[triang[i][1]]-ordpolygon[triang[i][3]];
    13261424    triangarea[i]=abs(det(N));
    13271425  }
    13281426  intvec ETA;        // stores the eta_ij
    1329   int etaij;         // stores the part of eta_ij during computations which comes from triangle areas
    1330   int seitenlaenge;  // stores the part of eta_ij during computations which comes from boundary facets
     1427  int etaij;         // stores the part of eta_ij during computations
     1428                     // which comes from triangle areas
     1429  int seitenlaenge;  // stores the part of eta_ij during computations
     1430                     // which comes from boundary facets
    13311431  list seiten;       // stores the lattice points on facets of the polygon
    13321432  intvec v;          // used to compute a facet length
    1333   // 3) store first in seiten[i] all lattice points on the facet connecting the ith vertex,
    1334   //    i.e. polygon[1][i], with the i+1st vertex, i.e. polygon[1][i+1], where we replace i+1
     1433  // 3) store first in seiten[i] all lattice points on the facet
     1434  //    connecting the ith vertex,
     1435  //    i.e. polygon[1][i], with the i+1st vertex, i.e. polygon[1][i+1],
     1436  //    where we replace i+1
    13351437  //    1 if i=size(polygon[1]);
    1336   //    then append the last entry of seiten once more at the very beginning of seiten, so
     1438  //    then append the last entry of seiten once more at the very
     1439  //    beginning of seiten, so
    13371440  //    that the index is shifted by one
    13381441  for (i=1;i<=size(polygon[1]);i++)
    … …  
    13591462      if ((polygon[1][j][2]==triang[k][1]) or (polygon[1][j][2]==triang[k][2]) or (polygon[1][j][2]==triang[k][3]))
    13601463      {
    1361         // ... if so, add the area of the triangle to etaij
     1464        // ... if so, add the area of the triangle to etaij 
    13621465        etaij=etaij+triangarea[k];
    1363         // then check if that triangle has a facet which is contained in one of the
     1466        // then check if that triangle has a facet which is contained
     1467        // in one of the
    13641468        // two facets of the polygon which are adjecent to the given vertex ...
    13651469        // these two facets are seiten[j] and seiten[j+1]
    … …  
    13751479              if ((seiten[n][l][2]==triang[k][m]) and (seiten[n][l][2]!=polygon[1][j][2]))
    13761480              {
    1377                 // if so, then compute the vector pointing from this lattice point to the vertex
     1481                // if so, then compute the vector pointing from this
     1482                // lattice point to the vertex
    13781483                v=polygon[1][j][1]-seiten[n][l][1];
    1379                 // and the lattice length of this vector has to be subtracted from etaij
     1484                // and the lattice length of this vector has to be
     1485                // subtracted from etaij
    13801486                etaij=etaij-abs(gcd(v[1],v[2]));
    13811487              }
    … …  
    13881494    ETA[polygon[1][j][2]]=etaij;
    13891495  }
    1390   // 5) compute the eta_ij for all lattice points on the facets of the polygon which are not vertices,
    1391   //    these are the lattice points in polygon[2][1] to polygon[2][size(polygon[1])]
     1496  // 5) compute the eta_ij for all lattice points on the facets
     1497  //    of the polygon which are not vertices, these are the
     1498  //    lattice points in polygon[2][1] to polygon[2][size(polygon[1])]
    13921499  for (i=1;i<=size(polygon[2]);i++)
    13931500  {
    13941501    for (j=1;j<=size(polygon[2][i]);j++)
    1395     {
     1502    {     
    13961503      // initialise etaij
    13971504      etaij=0;
    … …  
    14041511        if ((polygon[2][i][j][2]==triang[k][1]) or (polygon[2][i][j][2]==triang[k][2]) or (polygon[2][i][j][2]==triang[k][3]))
    14051512        {
    1406           // ... if so, add the area of the triangle to etaij
     1513          // ... if so, add the area of the triangle to etaij 
    14071514          etaij=etaij+triangarea[k];
    1408           // then check if that triangle has a facet which is contained in the
     1515          // then check if that triangle has a facet which is contained in the 
    14091516          // facet of the polygon which contains the lattice point in question,
    14101517          // this is the facet seiten[i+1];
    … …  
    14141521            // ... and for each lattice point in the triangle ...
    14151522            for (m=1;m<=size(triang[k]);m++)
    1416             {
     1523            {           
    14171524              // ... if they coincide and are not the vertex itself ...
    14181525              if ((seiten[i+1][l][2]==triang[k][m]) and (seiten[i+1][l][2]!=polygon[2][i][j][2]))
    14191526              {
    1420                 // if so, then compute the vector pointing from this lattice point to the vertex
     1527                // if so, then compute the vector pointing from
     1528                // this lattice point to the vertex
    14211529                v=polygon[2][i][j][1]-seiten[i+1][l][1];
    1422                 // and the lattice length of this vector contributes to seitenlaenge
     1530                // and the lattice length of this vector contributes
     1531                // to seitenlaenge
    14231532                seitenlaenge=seitenlaenge+abs(gcd(v[1],v[2]));
    14241533              }
    … …  
    14271536        }
    14281537      }
    1429       // if the lattice point was a vertex of any triangle in the triangulation ...
     1538      // if the lattice point was a vertex of any triangle
     1539      // in the triangulation ...
    14301540      if (etaij!=0)
    14311541      {
    … …  
    14511561      if ((polygon[3][j][2]==triang[k][1]) or (polygon[3][j][2]==triang[k][2]) or (polygon[3][j][2]==triang[k][3]))
    14521562      {
    1453         // ... if so, add the area of the triangle to etaij
     1563        // ... if so, add the area of the triangle to etaij 
    14541564        etaij=etaij+triangarea[k];
    14551565      }
    … …  
    14641574   "EXAMPLE:";
    14651575   echo=2;
    1466    // the lattice polygon spanned by the points (0,0), (3,0) and (0,3)
     1576   // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 
    14671577   // with all integer points as markings
    14681578   list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0),
    … …  
    14711581   // split the polygon in its vertices, its facets and its interior points
    14721582   list sp=splitPolygon(polygon);
    1473    // define a triangulation by connecting the only interior point
     1583   // define a triangulation by connecting the only interior point 
    14741584   //        with the vertices
    14751585   list triang=intvec(1,2,5),intvec(1,5,10),intvec(1,5,10);
    … …  
    14771587   eta(triang,sp);
    14781588}
     1589 
     1590/////////////////////////////////////////////////////////////////////////////
    14791591
    14801592proc findOrientedBoundary (list polygon)
    1481 "USAGE:      findOrientedBoundary(polygon); polygon list
    1482 ASSUME:      polygon is a list of integer vectors defining integer lattice points in the plane
    1483 RETURN:      list, l with the followin interpretation
    1484 @*                 l[1] = list of integer vectors such that the polygonal path defined by
    1485                           these is the boundary of the convex hull of the lattice points in polygon
    1486 @*                 l[2] = list, the redundant points in l[1] have been removed
     1593"USAGE: findOrientedBoundary(polygon); polygon list
     1594ASSUME: polygon is a list of integer vectors defining integer lattice points
     1595        in the plane
     1596RETURN: list, l with the followin interpretation
     1597@*            l[1] = list of integer vectors such that the polygonal path
     1598                     defined by these is the boundary of the convex hull of
     1599                     the lattice points in polygon
     1600@*            l[2] = list, the redundant points in l[1] have been removed
    14871601EXAMPLE:     example findOrientedBoundary;   shows an example"
    14881602{
    … …  
    15001614  }
    15011615  // check is the polygon is only a line segment given by more than two points;
    1502   // for this first compute sum of the absolute values of the determinants of the matrices whose
    1503   // rows are the vectors pointing from the first to the second point and from the
    1504   // the first point to the ith point for i=3,...,size(polygon); if this sum is zero
     1616  // for this first compute sum of the absolute values of the determinants
     1617  // of the matrices whose
     1618  // rows are the vectors pointing from the first to the second point
     1619  // and from the
     1620  // the first point to the ith point for i=3,...,size(polygon);
     1621  // if this sum is zero
    15051622  // then the polygon is a line segment and we have to find its end points
    15061623  d=0;
    … …  
    15141631    intmat laenge[size(polygon)][size(polygon)];
    15151632    intvec mp;
    1516     //   for this collect first all vectors pointing from one lattice point to the next,
     1633    //   for this collect first all vectors pointing from one lattice
     1634    //   point to the next,
    15171635    //   compute their pairwise angles and their lengths
    15181636    for (i=1;i<=size(polygon)-1;i++)
    1519     {
     1637    {     
    15201638      for (j=i+1;j<=size(polygon);j++)
    15211639      {
    … …  
    15411659    polygon=sortlistbyintvec(polygon,abstand);
    15421660    return(list(polygon,endpoints));
    1543   }
     1661  } 
    15441662  ///////////////////////////////////////////////////////////////
    15451663  list orderedvertices;  // stores the vertices in an ordered way
    1546   list minimisedorderedvertices;  // stores the vertices in an ordered way; redundant ones removed
    1547   list comparevertices; // stores vertices which should be compared to the testvertex
     1664  list minimisedorderedvertices;  // stores the vertices in an ordered way;
     1665                                  // redundant ones removed
     1666  list comparevertices; // stores vertices which should be compared to
     1667                        // the testvertex
    15481668  orderedvertices[1]=polygon[1]; // set the starting vertex
    15491669  minimisedorderedvertices[1]=polygon[1]; // set the starting vertex
    1550   intvec testvertex=polygon[1];  // the vertex to which the others have to be compared
    1551   intvec startvertex=polygon[1]; // keep the starting vertex to test, when the end is reached
    1552   int endtest;                    // is set to one, when the end is reached
    1553   int startvertexfound;// is 1, once for some testvertex a candidate for the next vertex has been found
     1670  intvec testvertex=polygon[1];  //vertex to which the others have to be compared
     1671  intvec startvertex=polygon[1]; // keep the starting vertex to test,
     1672                                 // when the end is reached
     1673  int endtest;                   // is set to one, when the end is reached
     1674  int startvertexfound;// is 1, once for some testvertex a candidate
     1675                       // for the next vertex has been found
    15541676  polygon=delete(polygon,1);    // delete the testvertex
    15551677  intvec v,w;
    15561678  int l=1;  // counts the vertices
    1557   // the basic idea is that a vertex can be the next one on the boundary if all other vertices
    1558   // ly to the right of the vector v pointing from the testvertex to this one; this can be tested
    1559   // by checking if the determinant of the 2x2-matrix with first column v and second column the vector w,
    1560   // pointing from the testvertex to the new vertex, is non-positive; if this is the case for all
    1561   // new vertices, then the one in consideration is a possible choice for the next vertex on the boundary
    1562   // and it is stored in naechste; we can then order the candidates according to their distance from
     1679  // the basic idea is that a vertex can be
     1680  // the next one on the boundary if all other vertices
     1681  // ly to the right of the vector v pointing
     1682  // from the testvertex to this one; this can be tested
     1683  // by checking if the determinant of the 2x2-matrix
     1684  // with first column v and second column the vector w,
     1685  // pointing from the testvertex to the new vertex,
     1686  // is non-positive; if this is the case for all
     1687  // new vertices, then the one in consideration is
     1688  // a possible choice for the next vertex on the boundary
     1689  // and it is stored in naechste; we can then order
     1690  // the candidates according to their distance from
    15631691  // the testvertex; then they occur on the boundary in that order!
    15641692  while (endtest==0)
    … …  
    15711699      v=polygon[i]-testvertex; // points from the testvertex to the ith vertex
    15721700      comparevertices=delete(polygon,i); // we needn't compare v to itself
    1573       // we should compare v to the startvertex-testvertex; in the first calling of the loop
    1574       // this is irrelevant since the difference will be zero; however, later on it will
    1575       // be vital, since we delete the vertices which we have already tested from the list
    1576       // of all vertices, and when all vertices on the boundary have been found we would
    1577       // therefore find a vertex in the interior as candidate; but always testing against
     1701      // we should compare v to the startvertex-testvertex;
     1702      // in the first calling of the loop
     1703      // this is irrelevant since the difference will be zero;
     1704      // however, later on it will
     1705      // be vital, since we delete the vertices
     1706      // which we have already tested from the list
     1707      // of all vertices, and when all vertices
     1708      // on the boundary have been found we would
     1709      // therefore find a vertex in the interior
     1710      // as candidate; but always testing against
    15781711      // the starting vertex, this can not happen
    1579       comparevertices[size(comparevertices)+1]=startvertex;
     1712      comparevertices[size(comparevertices)+1]=startvertex; 
    15801713      for (j=1;(j<=size(comparevertices)) and (d<=0);j++)
    15811714      {
    1582         w=comparevertices[j]-testvertex; // points form the testvertex to the jth vertex
     1715        w=comparevertices[j]-testvertex; // points form the testvertex
     1716                                         // to the jth vertex
    15831717        D=v,w;
    15841718        d=det(D);
    15851719      }
    1586       if (d<=0) // if all determinants are non-positive, then the ith vertex is a candidate
    1587       {
    1588         naechste[k]=list(polygon[i],i,scalarproduct(v,v)); // we store the vertex, its position, and its
    1589         k++;                                                // distance from the testvertex
     1720      if (d<=0) // if all determinants are non-positive,
     1721      { // then the ith vertex is a candidate
     1722        naechste[k]=list(polygon[i],i,scalarproduct(v,v));// we store the vertex,
     1723                                                          //its position, and its
     1724        k++; // distance from the testvertex
    15901725      }
    15911726    }
    15921727    if (size(naechste)>0) // then a candidate for the next vertex has been found
    1593     {
     1728    {     
    15941729      startvertexfound=1; // at least once a candidate has been found
    1595       naechste=sortlist(naechste,3);  //we order the candidates according to their distance from testvertex;
    1596       for (j=1;j<=size(naechste);j++) // then we store them in this order in orderedvertices
    1597       {
     1730      naechste=sortlist(naechste,3);  // we order the candidates according
     1731                                      // to their distance from testvertex;
     1732      for (j=1;j<=size(naechste);j++) // then we store them in this
     1733      { // order in orderedvertices
    15981734        l++;
    15991735        orderedvertices[l]=naechste[j][1];
    16001736      }
    1601       testvertex=naechste[size(naechste)][1];  // we store the last one as next testvertex;
    1602       minimisedorderedvertices[size(minimisedorderedvertices)+1]=testvertex; // store the next corner of NSD
    1603       naechste=sortlist(naechste,2);           // then we reorder the vertices according to their position
    1604       for (j=size(naechste);j>=1;j--)          // and we delete them from the vertices
     1737      testvertex=naechste[size(naechste)][1];  // we store the last one as
     1738                                               // next testvertex;
     1739      // store the next corner of NSD
     1740      minimisedorderedvertices[size(minimisedorderedvertices)+1]=testvertex;
     1741      naechste=sortlist(naechste,2); // then we reorder the vertices
     1742                                     // according to their position
     1743      for (j=size(naechste);j>=1;j--) // and we delete them from the vertices
    16051744      {
    16061745        polygon=delete(polygon,naechste[j][2]);
    16071746      }
    16081747    }
    1609     else // that means either that the vertex was inside the polygon,
    1610     {    // or that we have reached the last vertex on the boundary of the polytope
    1611       if (startvertexfound==0) // the vertex was in the interior; we delete it and start all over again
    1612       {
    1613         orderedvertices[1]=polygon[1];
    1614         minimisedorderedvertices[1]=polygon[1];
     1748    else // that means either that the vertex was inside the polygon,
     1749    {    // or that we have reached the last vertex on the boundary
     1750         // of the polytope
     1751      if (startvertexfound==0) // the vertex was in the interior;
     1752      { // we delete it and start all over again
     1753        orderedvertices[1]=polygon[1];
     1754        minimisedorderedvertices[1]=polygon[1];
    16151755        testvertex=polygon[1];
    16161756        startvertex=polygon[1];
    16171757        polygon=delete(polygon,1);
    16181758      }
    1619       else // we have reached the last vertex on the boundary of the polytope and can stop
    1620       {
     1759      else // we have reached the last vertex on the boundary of
     1760      { // the polytope and can stop
    16211761        endtest=1;
    16221762      }
    … …  
    16241764    kill naechste;
    16251765  }
    1626   // test if the first vertex in minimisedorderedvertices is on the same line with the second and
    1627   // the last, i.e. if we started our search in the middle of a face; if so, delete it
     1766  // test if the first vertex in minimisedorderedvertices
     1767  // is on the same line with the second and
     1768  // the last, i.e. if we started our search in the
     1769  // middle of a face; if so, delete it
    16281770  v=minimisedorderedvertices[2]-minimisedorderedvertices[1];
    16291771  w=minimisedorderedvertices[size(minimisedorderedvertices)]-minimisedorderedvertices[1];
    … …  
    16331775    minimisedorderedvertices=delete(minimisedorderedvertices,1);
    16341776  }
    1635   // test if the first vertex in minimisedorderedvertices is on the same line with the two
    1636   // last ones, i.e. if we started our search at the end of a face; if so, delete it
     1777  // test if the first vertex in minimisedorderedvertices
     1778  // is on the same line with the two
     1779  // last ones, i.e. if we started our search at the end of a face;
     1780  // if so, delete it
    16371781  v=minimisedorderedvertices[size(minimisedorderedvertices)-1]-minimisedorderedvertices[1];
    16381782  w=minimisedorderedvertices[size(minimisedorderedvertices)]-minimisedorderedvertices[1];
    … …  
    16611805
    16621806
     1807/////////////////////////////////////////////////////////////////////////////
     1808
    16631809proc cyclePoints (list triang,list points,int pt)
    16641810"USAGE:      cyclePoints(triang,points,pt)  triang,points list, pt int
    1665 ASSUME:      - points is a list of integer vectors describing the lattice points of a marked polygon;
    1666 @*           - triang is a list of integer vectors describing a triangulation of the marked polygon
    1667                in the sense that an integer vector of the form (i,j,k) describes the triangle formed
    1668                by polygon[i], polygon[j] and polygon[k];
    1669 @*           - pt is an integer between 1 and size(points), singling out a lattice point among
    1670                the marked points
    1671 PURPOSE:     consider the convex lattice polygon, say P, spanned by all lattice points in points which
    1672              in the triangulation triang are connected to the point points[pt]; the procedure
    1673              computes all marked points in points which ly on the boundary of that polygon, ordered
     1811ASSUME:      - points is a list of integer vectors describing the lattice
     1812               points of a marked polygon;
     1813@*           - triang is a list of integer vectors describing a triangulation
     1814               of the marked polygon in the sense that an integer vector of
     1815               the form (i,j,k) describes the triangle formed by polygon[i],
     1816               polygon[j] and polygon[k];
     1817@*           - pt is an integer between 1 and size(points), singling out a
     1818               lattice point among the marked points
     1819PURPOSE:     consider the convex lattice polygon, say P, spanned by all lattice
     1820             points in points which in the triangulation triang are connected
     1821             to the point points[pt]; the procedure computes all marked points
     1822             in points which ly on the boundary of that polygon, ordered
    16741823             clockwise
    1675 RETURN:      list, of integer vectors which are the coordinates of the lattice points on
    1676                    the boundary of the above mentioned polygon P, if this polygon is not the
    1677                    empty set (that would be the case if points[pt] is not a vertex of any
    1678                    triangle in the triangulation); otherwise return the empty list
     1824RETURN:      list, of integer vectors which are the coordinates of the lattice
     1825                   points on the boundary of the above mentioned polygon P, if
     1826                   this polygon is not the empty set (that would be the case if
     1827                   points[pt] is not a vertex of any triangle in the
     1828                   triangulation); otherwise return the empty list
    16791829EXAMPLE:     example cyclePoints;   shows an example"
    16801830{
    16811831  int i,j; // indices
    1682   list v;  // saves the indices of lattice points connected to the interior point in the triangulation
     1832  list v;  // saves the indices of lattice points connected to the
     1833           // interior point in the triangulation
    16831834  // save all points in triangulations containing pt in v
    16841835  for (i=1;i<=size(triang);i++)
    … …  
    17151866    pts[i]=points[v[i]];
    17161867  }
    1717   // consider the convex polytope spanned by the points in pts, find the points on the
     1868  // consider the convex polytope spanned by the points in pts,
     1869  // find the points on the
    17181870  // boundary and order them clockwise
    17191871  return(findOrientedBoundary(pts)[1]);
    … …  
    17231875   "EXAMPLE:";
    17241876   echo=2;
    1725    // the lattice polygon spanned by the points (0,0), (3,0) and (0,3)
     1877   // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 
    17261878   // with all integer points as markings
    17271879   list points=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0),
    17281880               intvec(0,0),intvec(2,1),intvec(0,1),intvec(1,2),
    17291881               intvec(0,2),intvec(0,3);
    1730    // define a triangulation
     1882   // define a triangulation 
    17311883   list triang=intvec(1,2,5),intvec(1,5,7),intvec(1,7,9),intvec(8,9,10),
    17321884               intvec(1,8,9),intvec(1,2,8);
    … …  
    17351887}
    17361888
     1889/////////////////////////////////////////////////////////////////////////////
     1890
    17371891proc latticeArea (list polygon)
    17381892"USAGE:  latticeArea(polygon);   polygon list
    17391893ASSUME:  polygon is a list of integer vectors in the plane
    1740 RETURN:  int, the lattice area of the convex hull of the lattice points in polygon,
    1741               i.e. twice the Euclidean area
     1894RETURN:  int, the lattice area of the convex hull of the lattice points in
     1895              polygon, i.e. twice the Euclidean area
    17421896EXAMPLE: example polygonlatticeArea;   shows an example"
    17431897{
    … …  
    17631917}
    17641918
     1919/////////////////////////////////////////////////////////////////////////////
     1920
    17651921proc picksFormula (list polygon)
    17661922"USAGE:  picksFormula(polygon);   polygon list
    1767 ASSUME:  polygon is a list of integer vectors in the plane and consider their convex hull C
    1768 RETURN:  list, L of three integersthe
     1923ASSUME:  polygon is a list of integer vectors in the plane and consider their
     1924         convex hull C
     1925RETURN:  list, L of three integersthe
    17691926@*             L[1] : the lattice area of C, i.e. twice the Euclidean area
    17701927@*             L[2] : the number of lattice points on the boundary of C
    17711928@*             L[3] : the number of interior lattice points of C
    1772 NOTE:    the integers in L are related by Pick's formula, namely: L[1]=L[2]+2*L[3]-2
     1929NOTE: the integers in L are related by Pick's formula, namely: L[1]=L[2]+2*L[3]-2
    17731930EXAMPLE: example picksFormula;   shows an example"
    17741931{
    … …  
    17911948    bdpts=bdpts+abs(gcd(edge[1],edge[2]));
    17921949  }
    1793   // Pick's formula says that the lattice area A, the number g of interior points and
     1950  // Pick's formula says that the lattice area A, the number g of interior
     1951  // points and
    17941952  // the number b of boundary points are connected by the formula: A=b+2g-2
    17951953  return(list(area,bdpts,(area-bdpts+2)/2));
    … …  
    18131971}
    18141972
     1973/////////////////////////////////////////////////////////////////////////////
     1974
    18151975proc ellipticNF (list polygon)
    18161976"USAGE:  ellipticNF(polygon);   polygon list
    1817 ASSUME:  polygon is a list of integer vectors in the plane such that their convex hull C
    1818          has precisely one interior lattice point; i.e. C is the Newton polygon of an
    1819          elliptic curve
    1820 PURPOSE: compute the normal form of the polygon with respect to the unimodular affine
    1821          transformations T=A*x+v; there are sixteen different normal forms
    1822          (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons and
    1823                    the number 12.  Amer. Math. Monthly  107  (2000),  no. 3, 238--250.)
     1977ASSUME:  polygon is a list of integer vectors in the plane such that their
     1978         convex hull C has precisely one interior lattice point; i.e. C is the
     1979         Newton polygon of an elliptic curve
     1980PURPOSE: compute the normal form of the polygon with respect to the unimodular
     1981         affine transformations T=A*x+v; there are sixteen different normal forms
     1982         (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons
     1983                   and the number 12.  Amer. Math. Monthly  107  (2000),  no. 3,
     1984                   238--250.)
    18241985RETURN:  list, L such that
    1825 @*             L[1] : list whose entries are the vertices of the normal form of the polygon
     1986@*             L[1] : list whose entries are the vertices of the normal form of
     1987                      the polygon
    18261988@*             L[2] : the matrix A of the unimodular transformation
    18271989@*             L[3] : the translation vector v of the unimodular transformation
    1828 @*             L[4] : list such that the ith entry is the image of polygon[i] under the
    1829                       unimodular transformation T
     1990@*             L[4] : list such that the ith entry is the image of polygon[i]
     1991                      under the unimodular transformation T
    18301992EXAMPLE: example ellipticNF;   shows an example"
    18311993{
    18321994  int i;            // index
    18331995  intvec edge;      // stores the vector of an edge
    1834   intvec boundary;  // stores the lattice lengths of the edges of the Newton cylce
     1996  intvec boundary;  // stores lattice lengths of the edges of the Newton cylce
    18351997  // find the vertices of the Newton cycle and order it clockwise
    18361998  list pg=findOrientedBoundary(polygon)[2];
    … …  
    18582020  intvec trans;    // stores the vector by which we have to translate the polygon
    18592021  intmat A[2][2];  // stores the matrix by which we have to transform the polygon
    1860   matrix M[3][3];  // stores the projective coordinates of the points which are to be transformed
    1861   matrix N[3][3];  // stores the projective coordinates of the points to which M is to be transformed
    1862   intmat T[3][3];  // stores the unimodular affine transformation in projective form
     2022  matrix M[3][3];  // stores the projective coordinates of the points
     2023                   // which are to be transformed
     2024  matrix N[3][3];  // stores the projective coordinates of the points to
     2025                   // which M is to be transformed
     2026  intmat T[3][3];  // stores the unimodular affine transformation in
     2027                   // projective form
    18632028  // add the second point of pg once again at the end
    18642029  pg=insert(pg,pg[2],size(pg));
    1865   // if there is only one edge which has the maximal number of lattice points, then M should be:
     2030  // if there is only one edge which has the maximal number of lattice points,
     2031  // then M should be:
    18662032  M=pg[max],1,pg[max+1],1,pg[max+2],1;
    18672033  // consider the 16 different cases which can occur:
    … …  
    19522118    M=pg[max],1,pg[max+1],1,pg[max+2],1;
    19532119    // the orientation of the polygon matters
    1954     A=pg[max-1]-pg[max],pg[max+1]-pg[max];
     2120    A=pg[max-1]-pg[max],pg[max+1]-pg[max];   
    19552121    if (det(A)==4)
    19562122    {
    … …  
    20012167    {
    20022168      max++;
    2003     }
     2169    }   
    20042170    M=pg[max],1,pg[max+1],1,pg[max+2],1;
    20052171    N=0,1,1,1,2,1,2,1,1;
    … …  
    20642230   // the vertices of the normal form are
    20652231   nf[1];
    2066    // it has been transformed by the unimodular affine transformation A*x+v
     2232   // it has been transformed by the unimodular affine transformation A*x+v 
    20672233   // with matrix A
    20682234   nf[2];
    … …  
    20762242
    20772243
     2244/////////////////////////////////////////////////////////////////////////////
     2245
    20782246proc ellipticNFDB (int n,list #)
    20792247"USAGE:  ellipticNFDB(n[,#]);   n int, # list
    20802248ASSUME:  n is an intger between 1 and 16
    2081 PURPOSE: this is a database storing the 16 normal forms of planar polygons with
     2249PURPOSE: this is a database storing the 16 normal forms of planar polygons with 
    20822250         precisely one interior point up to unimodular affine transformations
    2083 @*       (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons and
    2084                    the number 12.  Amer. Math. Monthly  107  (2000),  no. 3, 238--250.)
     2251@*       (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons
     2252                   and the number 12.  Amer. Math. Monthly  107  (2000),  no. 3,
     2253                   238--250.)
    20852254RETURN:  list, L such that
    2086 @*             L[1] : list whose entries are the vertices of the nth normal form
    2087 @*             L[2] : list whose entries are all the lattice points of the nth normal form
    2088 @*             L[3] : only present if the optional parameter # is present, and then
    2089                       it is a polynomial in the variables (x,y) whose Newton polygon
    2090                       is the nth normal form
    2091 NOTE:    the optional parameter is only allowed if the basering has the variables x and y
     2255@*             L[1] : list whose entries are the vertices of the nth normal form
     2256@*             L[2] : list whose entries are all the lattice points of the
     2257                      nth normal form
     2258@*             L[3] : only present if the optional parameter # is present, and
     2259                      then it is a polynomial in the variables (x,y) whose
     2260                      Newton polygon is the nth normal form
     2261NOTE:    the optional parameter is only allowed if the basering has the
     2262         variables x and y
    20922263EXAMPLE: example ellipticNFDB;   shows an example"
    20932264{
    … …  
    21392310proc polymakeKeepTmpFiles (int i)
    21402311"USAGE:  polymakeKeepTmpFiles(int i);   i int
    2141 PURPOSE: some procedures create files in the directory /tmp which are used for
     2312PURPOSE: some procedures create files in the directory /tmp which are used for 
    21422313         computations with polymake respectively topcom; these will be removed
    2143          when the corresponding procedure is left; however, it might be desireable
    2144          to keep them for further computations with either polymake or topcom; this
    2145          can be achieved by this procedure; call the procedure as:
    2146 @*       - polymakeKeepTmpFiles(1);  - then the files will be kept
    2147 @*       - polymakeKeepTmpFiles(0);  - then the files will be removed in the future
     2314         when the corresponding procedure is left; however, it might be
     2315         desireable to keep them for further computations with either polymake or
     2316         topcom; this can be achieved by this procedure; call the procedure as:
     2317@*       - polymakeKeepTmpFiles(1); - then the files will be kept
     2318@*       - polymakeKeepTmpFiles(0); - then files will be removed in the future
    21482319RETURN:  none"
    21492320{
    … …  
    21842355static proc scalarproduct (intvec w,intvec v)
    21852356"USAGE:      scalarproduct(w,v); w,v intvec
    2186 ASSUME:      w and v are integer vectors of the same length
     2357ASSUME:      w and v are integer vectors of the same length 
    21872358RETURN:      int, the scalarproduct of v and w
    21882359NOTE:        the procedure is called by findOrientedBoundary"
    … …  
    22312402  {
    22322403    int m=nrows(M);
    2233 
     2404   
    22342405  }
    22352406  else
    … …  
    22892460  {
    22902461    return("");
    2291 
     2462   
    22922463  }
    22932464  if (i==1)
    … …  
    23992570        k++;
    24002571      }
    2401       else
     2572      else 
    24022573      {
    24032574        stop=1;
    … …  
    24422613        k++;
    24432614      }
    2444       else
     2615      else 
    24452616      {
    24462617        stop=1;
    … …  
    24912662static proc polygonToCoordinates (list points)
    24922663"USAGE:      polygonToCoordinates(points);   points list
    2493 ASSUME:      points is a list of integer vectors each of size two describing the
    2494              marked points of a convex lattice polygon like the output of polygonDB
    2495 RETURN:      list, the first entry is a string representing the coordinates corresponding
    2496                    to the latticpoints seperated by commata
    2497                    the second entry is a list where the ith entry is a string representing
    2498                    the coordinate of corresponding to the ith lattice point
    2499                    the third entry is the latex format of the first entry
     2664ASSUME:      points is a list of integer vectors each of size two describing the
     2665             marked points of a convex lattice polygon like the output of
     2666             polygonDB
     2667RETURN:      list, the first entry is a string representing the coordinates
     2668                   corresponding to the latticpoints seperated by commata
     2669                   the second entry is a list where the ith entry is a string
     2670                   representing the coordinate of corresponding to the ith
     2671                   lattice point the third entry is the latex format of the
     2672                   first entry
    25002673NOTE:        the procedure is called by fan"
    25012674{
    … …  
    25132686  return(list(coord,coords,latex));
    25142687}
    2515 
    2516 
Note: See TracChangeset for help on using the changeset viewer.