[7e8485] | 1 | version="version oldpolymake.lib 4.0.0.0 Jun_2013 "; |
---|
[b0732eb] | 2 | category="Tropical Geometry"; |
---|
| 3 | info=" |
---|
[7e8485] | 4 | LIBRARY: oldpolymake.lib Computations with polytopes and fans, |
---|
| 5 | interface to polymake and TOPCOM |
---|
[b0732eb] | 6 | AUTHOR: Thomas Markwig, email: keilen@mathematik.uni-kl.de |
---|
| 7 | |
---|
| 8 | WARNING: |
---|
| 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! |
---|
[7e8485] | 11 | For more detailed information see IMPORTANT NOTE respectively consult the |
---|
[b0732eb] | 12 | help string of the procedures. |
---|
| 13 | |
---|
[7e8485] | 14 | The conventions used in this library for polytopes and fans, e.g. the |
---|
| 15 | length and labeling of their vertices resp. rays, differs from the conventions |
---|
| 16 | used in polymake and thus from the conventions used in the polymake |
---|
| 17 | extension polymake.so of Singular. We recommend to use the newer polymake.so |
---|
| 18 | whenever possible. |
---|
| 19 | |
---|
| 20 | IMPORTANT NOTE: |
---|
| 21 | Even though this is a Singular library for computing polytopes and fans |
---|
| 22 | such as the Newton polytope or the Groebner fan of a polynomial, most of |
---|
| 23 | the hard computations are NOT done by Singular but by the program |
---|
[b0732eb] | 24 | @* - polymake by Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt |
---|
[7e8485] | 25 | @* (see http://www.math.tu-berlin.de/polymake/), |
---|
| 26 | @* respectively (only in the procedure triangulations) by the program |
---|
| 27 | @* - topcom by Joerg Rambau, Universitaet Bayreuth (see |
---|
| 28 | @* http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM); |
---|
| 29 | @* this library should rather be seen as an interface which allows to use a |
---|
| 30 | (very limited) number of options which polymake respectively topcom offers |
---|
| 31 | to compute with polytopes and fans and to make the results available in |
---|
| 32 | Singular for further computations; |
---|
[b0732eb] | 33 | moreover, the user familiar with Singular does not have to learn the syntax |
---|
[7e8485] | 34 | of polymake or topcom, if the options offered here are sufficient for his |
---|
[b0732eb] | 35 | purposes. |
---|
[7e8485] | 36 | @* Note, though, that the procedures concerned with planar polygons are |
---|
[b0732eb] | 37 | independent of both, polymake and topcom. |
---|
| 38 | |
---|
[7e8485] | 39 | PROCEDURES USING POLYMAKE: |
---|
| 40 | polymakePolytope() computes the vertices of a polytope using polymake |
---|
| 41 | newtonPolytope() computes the Newton polytope of a polynomial |
---|
| 42 | newtonPolytopeLP() computes the lattice points of the Newton polytope |
---|
| 43 | normalFan() computes the normal fan of a polytope |
---|
| 44 | groebnerFan() computes the Groebner fan of a polynomial |
---|
| 45 | |
---|
| 46 | PROCEDURES USING TOPCOM: |
---|
| 47 | triangulations() computes all triangulations of a marked polytope |
---|
| 48 | secondaryPolytope() computes the secondary polytope of a marked polytope |
---|
| 49 | |
---|
| 50 | PROCEDURES USING POLYMAKE AND TOPCOM: |
---|
| 51 | secondaryFan() computes the secondary fan of a marked polytope |
---|
| 52 | |
---|
| 53 | PROCEDURES CONERNED WITH PLANAR POLYGONS: |
---|
| 54 | cycleLength() computes the cycleLength of cycle |
---|
| 55 | splitPolygon() splits a marked polygon into vertices, facets, interior points |
---|
| 56 | eta() computes the eta-vector of a triangulation |
---|
| 57 | findOrientedBoundary() computes the boundary of a convex hull |
---|
| 58 | cyclePoints() computes lattice points connected to some lattice point |
---|
| 59 | latticeArea() computes the lattice area of a polygon |
---|
| 60 | picksFormula() computes the ingrediants of Pick's formula for a polygon |
---|
| 61 | ellipticNF() computes the normal form of an elliptic polygon |
---|
| 62 | ellipticNFDB() displays the 16 normal forms of elliptic polygons |
---|
[b0732eb] | 63 | |
---|
| 64 | KEYWORDS: polytope; fan; secondary fan; secondary polytope; polymake; |
---|
[7e8485] | 65 | Newton polytope; Groebner fan |
---|
[b0732eb] | 66 | "; |
---|
| 67 | |
---|
| 68 | //////////////////////////////////////////////////////////////////////////////// |
---|
| 69 | /// Auxilary Static Procedures in this Library |
---|
| 70 | //////////////////////////////////////////////////////////////////////////////// |
---|
| 71 | /// - scalarproduct |
---|
| 72 | /// - intmatcoldelete |
---|
| 73 | /// - intmatconcat |
---|
| 74 | /// - sortlist |
---|
| 75 | /// - minInList |
---|
| 76 | /// - stringdelete |
---|
| 77 | /// - abs |
---|
| 78 | /// - commondenominator |
---|
| 79 | /// - maxPosInIntvec |
---|
| 80 | /// - maxPosInIntmat |
---|
| 81 | /// - sortintvec |
---|
| 82 | /// - matrixtointmat |
---|
| 83 | //////////////////////////////////////////////////////////////////////////////// |
---|
| 84 | |
---|
| 85 | //////////////////////////////////////////////////////////////////////////////// |
---|
| 86 | LIB "poly.lib"; |
---|
| 87 | LIB "linalg.lib"; |
---|
| 88 | LIB "random.lib"; |
---|
[7e8485] | 89 | LIB "polymake.so"; |
---|
[b0732eb] | 90 | //////////////////////////////////////////////////////////////////////////////// |
---|
| 91 | |
---|
| 92 | |
---|
| 93 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 94 | /// PROCEDURES USING POLYMAKE |
---|
| 95 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 96 | |
---|
[7e8485] | 97 | proc polymakePolytope (intmat points) |
---|
| 98 | "USAGE: polymakePolytope(points); polytope intmat |
---|
| 99 | ASSUME: each row of points gives the coordinates of a lattice point of a |
---|
| 100 | polytope with their affine coordinates as given by the output of |
---|
[b0732eb] | 101 | secondaryPolytope |
---|
[7e8485] | 102 | PURPOSE: the procedure calls polymake to compute the vertices of the polytope |
---|
[b0732eb] | 103 | as well as its dimension and information on its facets |
---|
[7e8485] | 104 | RETURN: list, L with four entries |
---|
[b0732eb] | 105 | @* L[1] : an integer matrix whose rows are the coordinates of vertices |
---|
[7e8485] | 106 | of the polytope |
---|
[b0732eb] | 107 | @* L[2] : the dimension of the polytope |
---|
[7e8485] | 108 | @* L[3] : a list whose ith entry explains to which vertices the |
---|
| 109 | ith vertex of the Newton polytope is connected |
---|
| 110 | -- i.e. L[3][i] is an integer vector and an entry k in |
---|
| 111 | there means that the vertex L[1][i] is connected to the |
---|
[b0732eb] | 112 | vertex L[1][k] |
---|
[7e8485] | 113 | @* L[4] : an matrix of type bigintmat whose rows mulitplied by |
---|
| 114 | (1,var(1),...,var(nvar)) give a linear system of equations |
---|
[b0732eb] | 115 | describing the affine hull of the polytope, |
---|
| 116 | i.e. the smallest affine space containing the polytope |
---|
[7e8485] | 117 | NOTE: - for its computations the procedure calls the program polymake by |
---|
| 118 | Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt; |
---|
| 119 | it therefore is necessary that this program is installed in order |
---|
[b0732eb] | 120 | to use this procedure; |
---|
| 121 | see http://www.math.tu-berlin.de/polymake/ |
---|
[7e8485] | 122 | @* - note that in the vertex edge graph we have changed the polymake |
---|
| 123 | convention which starts indexing its vertices by zero while we start |
---|
[b0732eb] | 124 | with one ! |
---|
| 125 | EXAMPLE: example polymakePolytope; shows an example" |
---|
| 126 | { |
---|
[7e8485] | 127 | // add a first column to polytope as homogenising coordinate |
---|
| 128 | points=intmatAddFirstColumn(points,"points"); |
---|
| 129 | polytope polytop=polytopeViaPoints(points); |
---|
| 130 | list graph=vertexAdjacencyGraph(polytop)[2]; |
---|
[b0732eb] | 131 | int i,j; |
---|
[7e8485] | 132 | for (i=1;i<=size(graph);i++) |
---|
[b0732eb] | 133 | { |
---|
[7e8485] | 134 | for (j=1;j<=size(graph[i]);j++) |
---|
[b0732eb] | 135 | { |
---|
[7e8485] | 136 | graph[i][j]=graph[i][j]+1; |
---|
[b0732eb] | 137 | } |
---|
| 138 | } |
---|
[7e8485] | 139 | return(list(intmatcoldelete(vertices(polytop),1),dimension(polytop),graph,equations(polytop))); |
---|
[b0732eb] | 140 | } |
---|
| 141 | example |
---|
| 142 | { |
---|
| 143 | "EXAMPLE:"; |
---|
| 144 | echo=2; |
---|
[7e8485] | 145 | // the lattice points of the unit square in the plane |
---|
[b0732eb] | 146 | list points=intvec(0,0),intvec(0,1),intvec(1,0),intvec(1,1); |
---|
| 147 | // the secondary polytope of this lattice point configuration is computed |
---|
| 148 | intmat secpoly=secondaryPolytope(points)[1]; |
---|
| 149 | list np=polymakePolytope(secpoly); |
---|
| 150 | // the vertices of the secondary polytope are: |
---|
| 151 | np[1]; |
---|
| 152 | // its dimension is |
---|
| 153 | np[2]; |
---|
| 154 | // np[3] contains information how the vertices are connected to each other, |
---|
| 155 | // e.g. the first vertex (number 0) is connected to the second one |
---|
| 156 | np[3][1]; |
---|
| 157 | // the affine hull has the equation |
---|
| 158 | ring r=0,x(1..4),dp; |
---|
| 159 | matrix M[5][1]=1,x(1),x(2),x(3),x(4); |
---|
[7e8485] | 160 | intmat(np[4])*M; |
---|
[b0732eb] | 161 | } |
---|
| 162 | |
---|
| 163 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 164 | |
---|
[7e8485] | 165 | proc newtonPolytope (poly f) |
---|
| 166 | "USAGE: newtonPolytope(f); f poly |
---|
| 167 | RETURN: list, L with four entries |
---|
[b0732eb] | 168 | @* L[1] : an integer matrix whose rows are the coordinates of vertices |
---|
| 169 | of the Newton polytope of f |
---|
| 170 | @* L[2] : the dimension of the Newton polytope of f |
---|
[7e8485] | 171 | @* L[3] : a list whose ith entry explains to which vertices the |
---|
| 172 | ith vertex of the Newton polytope is connected |
---|
| 173 | -- i.e. L[3][i] is an integer vector and an entry k in |
---|
[b0732eb] | 174 | there means that the vertex L[1][i] is |
---|
| 175 | connected to the vertex L[1][k] |
---|
[7e8485] | 176 | @* L[4] : an matrix of type bigintmat whose rows mulitplied by |
---|
| 177 | (1,var(1),...,var(nvar)) give a linear system of equations |
---|
[b0732eb] | 178 | describing the affine hull of the Newton polytope, i.e. the |
---|
| 179 | smallest affine space containing the Newton polytope |
---|
[7e8485] | 180 | NOTE: - if we replace the first column of L[4] by zeros, i.e. if we move |
---|
| 181 | the affine hull to the origin, then we get the equations for the |
---|
| 182 | orthogonal complement of the linearity space of the normal fan dual |
---|
[b0732eb] | 183 | to the Newton polytope, i.e. we get the EQUATIONS that |
---|
| 184 | we need as input for polymake when computing the normal fan |
---|
| 185 | @* - the procedure calls for its computation polymake by Ewgenij Gawrilow, |
---|
| 186 | TU Berlin and Michael Joswig, so it only works if polymake is installed; |
---|
| 187 | see http://www.math.tu-berlin.de/polymake/ |
---|
[7e8485] | 188 | EXAMPLE: example newtonPolytope; shows an example" |
---|
[b0732eb] | 189 | { |
---|
| 190 | int i,j; |
---|
[7e8485] | 191 | // compute the list of exponent vectors of the polynomial, |
---|
[b0732eb] | 192 | // which are the lattice points |
---|
| 193 | // whose convex hull is the Newton polytope of f |
---|
| 194 | intmat exponents[size(f)][nvars(basering)]; |
---|
| 195 | while (f!=0) |
---|
| 196 | { |
---|
| 197 | i++; |
---|
| 198 | exponents[i,1..nvars(basering)]=leadexp(f); |
---|
| 199 | f=f-lead(f); |
---|
| 200 | } |
---|
| 201 | // call polymakePolytope with exponents |
---|
[7e8485] | 202 | return(polymakePolytope(exponents)); |
---|
[b0732eb] | 203 | } |
---|
| 204 | example |
---|
| 205 | { |
---|
| 206 | "EXAMPLE:"; |
---|
| 207 | echo=2; |
---|
| 208 | ring r=0,(x,y,z),dp; |
---|
| 209 | matrix M[4][1]=1,x,y,z; |
---|
| 210 | poly f=y3+x2+xy+2xz+yz+z2+1; |
---|
| 211 | // the Newton polytope of f is |
---|
[7e8485] | 212 | list np=newtonPolytope(f); |
---|
[b0732eb] | 213 | // the vertices of the Newton polytope are: |
---|
| 214 | np[1]; |
---|
| 215 | // its dimension is |
---|
| 216 | np[2]; |
---|
| 217 | // np[3] contains information how the vertices are connected to each other, |
---|
[7e8485] | 218 | // e.g. the first vertex (number 0) is connected to the second, third and |
---|
[b0732eb] | 219 | // fourth vertex |
---|
| 220 | np[3][1]; |
---|
| 221 | ////////////////////////// |
---|
| 222 | f=x2-y3; |
---|
| 223 | // the Newton polytope of f is |
---|
[7e8485] | 224 | np=newtonPolytope(f); |
---|
[b0732eb] | 225 | // the vertices of the Newton polytope are: |
---|
| 226 | np[1]; |
---|
| 227 | // its dimension is |
---|
[7e8485] | 228 | np[2]; |
---|
| 229 | // the Newton polytope is contained in the affine space given |
---|
[b0732eb] | 230 | // by the equations |
---|
[7e8485] | 231 | intmat(np[4])*M; |
---|
[b0732eb] | 232 | } |
---|
| 233 | |
---|
| 234 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 235 | |
---|
| 236 | proc newtonPolytopeLP (poly f) |
---|
| 237 | "USAGE: newtonPolytopeLP(f); f poly |
---|
[7e8485] | 238 | RETURN: list, the exponent vectors of the monomials occuring in f, |
---|
[b0732eb] | 239 | i.e. the lattice points of the Newton polytope of f |
---|
| 240 | EXAMPLE: example normalFan; shows an example" |
---|
| 241 | { |
---|
| 242 | list np; |
---|
| 243 | int i=1; |
---|
| 244 | while (f!=0) |
---|
| 245 | { |
---|
| 246 | np[i]=leadexp(f); |
---|
| 247 | f=f-lead(f); |
---|
| 248 | i++; |
---|
| 249 | } |
---|
| 250 | return(np); |
---|
| 251 | } |
---|
| 252 | example |
---|
| 253 | { |
---|
| 254 | "EXAMPLE:"; |
---|
| 255 | echo=2; |
---|
| 256 | ring r=0,(x,y,z),dp; |
---|
| 257 | poly f=y3+x2+xy+2xz+yz+z2+1; |
---|
| 258 | // the lattice points of the Newton polytope of f are |
---|
| 259 | newtonPolytopeLP(f); |
---|
| 260 | } |
---|
| 261 | |
---|
| 262 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 263 | |
---|
| 264 | proc normalFan (intmat vertices,intmat affinehull,list graph,int er,list #) |
---|
| 265 | "USAGE: normalFan (vert,aff,graph,rays,[,#]); vert,aff intmat, graph list, rays int, # string |
---|
[7e8485] | 266 | ASSUME: - vert is an integer matrix whose rows are the coordinate of |
---|
| 267 | the vertices of a convex lattice polytope; |
---|
[b0732eb] | 268 | @* - aff describes the affine hull of this polytope, i.e. |
---|
[7e8485] | 269 | the smallest affine space containing it, in the following sense: |
---|
| 270 | denote by n the number of columns of vert, then multiply aff by |
---|
| 271 | (1,x(1),...,x(n)) and set the resulting terms to zero in order to |
---|
[b0732eb] | 272 | get the equations for the affine hull; |
---|
[7e8485] | 273 | @* - the ith entry of graph is an integer vector describing to which |
---|
| 274 | vertices the ith vertex is connected, i.e. a k as entry means that |
---|
[b0732eb] | 275 | the vertex vert[i] is connected to vert[k]; |
---|
[7e8485] | 276 | @* - the integer rays is either one (if the extreme rays should be |
---|
[b0732eb] | 277 | computed) or zero (otherwise) |
---|
[7e8485] | 278 | RETURN: list, the ith entry of L[1] contains information about the cone in the |
---|
| 279 | normal fan dual to the ith vertex of the polytope |
---|
| 280 | @* L[1][i][1] = integer matrix representing the inequalities which |
---|
[b0732eb] | 281 | describe the cone dual to the ith vertex |
---|
[7e8485] | 282 | @* L[1][i][2] = a list which contains the inequalities represented |
---|
| 283 | by L[i][1] as a list of strings, where we use the |
---|
[b0732eb] | 284 | variables x(1),...,x(n) |
---|
| 285 | @* L[1][i][3] = only present if 'er' is set to 1; in that case it is |
---|
[7e8485] | 286 | an interger matrix whose rows are the extreme rays |
---|
[b0732eb] | 287 | of the cone |
---|
[7e8485] | 288 | @* L[2] = is an integer matrix whose rows span the linearity space |
---|
| 289 | of the fan, i.e. the linear space which is contained in |
---|
[b0732eb] | 290 | each cone |
---|
| 291 | NOTE: - the procedure calls for its computation polymake by Ewgenij Gawrilow, |
---|
[7e8485] | 292 | TU Berlin and Michael Joswig, so it only works if polymake is |
---|
[b0732eb] | 293 | installed; |
---|
| 294 | see http://www.math.tu-berlin.de/polymake/ |
---|
[7e8485] | 295 | @* - in the optional argument # it is possible to hand over other names |
---|
[b0732eb] | 296 | for the variables to be used -- be careful, the format must be correct |
---|
[7e8485] | 297 | and that is not tested, e.g. if you want the variable names to be |
---|
| 298 | u00,u10,u01,u11 then you must hand over the string u11,u10,u01,u11 |
---|
[b0732eb] | 299 | EXAMPLE: example normalFan; shows an example" |
---|
| 300 | { |
---|
| 301 | list ineq; // stores the inequalities of the cones |
---|
| 302 | int i,j,k; |
---|
[7e8485] | 303 | // we work over the following ring |
---|
[b0732eb] | 304 | execute("ring ineqring=0,x(1.."+string(ncols(vertices))+"),lp;"); |
---|
| 305 | string greatersign=">"; |
---|
| 306 | // create the variable names |
---|
| 307 | if (size(#)>0) |
---|
| 308 | { |
---|
| 309 | if (typeof(#[1])=="string") |
---|
| 310 | { |
---|
| 311 | kill ineqring; |
---|
| 312 | execute("ring ineqring=0,("+#[1]+"),lp;"); |
---|
| 313 | } |
---|
| 314 | if (size(#)>1) |
---|
| 315 | { |
---|
| 316 | greatersign="<"; |
---|
| 317 | } |
---|
| 318 | } |
---|
| 319 | ////////////////////////////////////////////////////////////////// |
---|
| 320 | // Compute first the inequalities of the cones |
---|
| 321 | ////////////////////////////////////////////////////////////////// |
---|
| 322 | matrix VAR[1][ncols(vertices)]=maxideal(1); |
---|
| 323 | matrix EXP[ncols(vertices)][1]; |
---|
| 324 | poly p,pl,pr; |
---|
| 325 | // consider all vertices of the polytope |
---|
| 326 | for (i=1;i<=nrows(vertices);i++) |
---|
| 327 | { |
---|
[7e8485] | 328 | // first we produce for each vertex in the polytope |
---|
[b0732eb] | 329 | // the inequalities describing the dual cone in the normal fan |
---|
[7e8485] | 330 | list pp; // contain strings representing the inequalities |
---|
[b0732eb] | 331 | // describing the normal cone |
---|
[7e8485] | 332 | intmat ie[size(graph[i])][ncols(vertices)]; // contains the inequalities |
---|
[b0732eb] | 333 | // as rows |
---|
[7e8485] | 334 | // consider all the vertices to which the ith vertex in the |
---|
[b0732eb] | 335 | // polytope is connected by an edge |
---|
| 336 | for (j=1;j<=size(graph[i]);j++) |
---|
| 337 | { |
---|
| 338 | // produce the vector ie_j pointing from the jth vertex to the ith vertex; |
---|
[7e8485] | 339 | // this will be the jth inequality for the cone in the normal fan dual to |
---|
[b0732eb] | 340 | // the ith vertex |
---|
| 341 | ie[j,1..ncols(vertices)]=vertices[i,1..ncols(vertices)]-vertices[graph[i][j],1..ncols(vertices)]; |
---|
| 342 | EXP=ie[j,1..ncols(vertices)]; |
---|
| 343 | // build a linear polynomial with the entries of ie_j as coefficients |
---|
| 344 | p=(VAR*EXP)[1,1]; |
---|
| 345 | pl,pr=0,0; |
---|
[7e8485] | 346 | // separate the terms with positive coefficients in p from |
---|
[b0732eb] | 347 | // those with negative coefficients |
---|
| 348 | for (k=1;k<=size(p);k++) |
---|
| 349 | { |
---|
| 350 | if (leadcoef(p[k])<0) |
---|
| 351 | { |
---|
| 352 | pr=pr-p[k]; |
---|
| 353 | } |
---|
| 354 | else |
---|
| 355 | { |
---|
| 356 | pl=pl+p[k]; |
---|
| 357 | } |
---|
| 358 | } |
---|
[7e8485] | 359 | // build the string which represents the jth inequality |
---|
[b0732eb] | 360 | // for the cone dual to the ith vertex |
---|
[7e8485] | 361 | // as polynomial inequality of type string, and store this |
---|
[b0732eb] | 362 | // in the list pp as jth entry |
---|
| 363 | pp[j]=string(pl)+" "+greatersign+" "+string(pr); |
---|
| 364 | } |
---|
| 365 | // all inequalities for the ith vertex are stored in the list ineq |
---|
| 366 | ineq[i]=list(ie,pp); |
---|
| 367 | kill ie,pp; // kill certain lists |
---|
| 368 | } |
---|
| 369 | // remove the first column of affine hull to compute the linearity space |
---|
[7e8485] | 370 | intmat linearity[1][ncols(vertices)]; |
---|
| 371 | if (nrows(affinehull)>0) |
---|
| 372 | { |
---|
| 373 | linearity=intmatcoldelete(affinehull,1); |
---|
| 374 | } |
---|
[b0732eb] | 375 | ////////////////////////////////////////////////////////////////// |
---|
| 376 | // Compute next the extreme rays of the cones |
---|
| 377 | ////////////////////////////////////////////////////////////////// |
---|
| 378 | if (er==1) |
---|
| 379 | { |
---|
| 380 | list extremerays; // keeps the result |
---|
[7e8485] | 381 | cone kegel; |
---|
| 382 | intmat linearspan=intmatAddFirstColumn(linearity,"rays"); |
---|
[b0732eb] | 383 | intmat M; // the matrix keeping the inequalities |
---|
| 384 | for (i=1;i<=size(ineq);i++) |
---|
| 385 | { |
---|
[7e8485] | 386 | kegel=coneViaInequalities(intmatAddFirstColumn(ineq[i][1],"rays"),linearspan); |
---|
| 387 | extremerays[i]=intmatcoldelete(rays(kegel),1); |
---|
[b0732eb] | 388 | } |
---|
| 389 | for (i=1;i<=size(ineq);i++) |
---|
| 390 | { |
---|
| 391 | ineq[i]=ineq[i]+list(extremerays[i]); |
---|
| 392 | } |
---|
| 393 | } |
---|
| 394 | // get the linearity space |
---|
[7e8485] | 395 | return(list(ineq,linearity)); |
---|
[b0732eb] | 396 | } |
---|
| 397 | example |
---|
| 398 | { |
---|
| 399 | "EXAMPLE:"; |
---|
| 400 | echo=2; |
---|
| 401 | ring r=0,(x,y,z),dp; |
---|
| 402 | matrix M[4][1]=1,x,y,z; |
---|
| 403 | poly f=y3+x2+xy+2xz+yz+z2+1; |
---|
| 404 | // the Newton polytope of f is |
---|
[7e8485] | 405 | list np=newtonPolytope(f); |
---|
[b0732eb] | 406 | // the Groebner fan of f, i.e. the normal fan of the Newton polytope |
---|
| 407 | list gf=normalFan(np[1],np[4],np[3],1,"x,y,z"); |
---|
| 408 | // the number of cones in the Groebner fan of f is: |
---|
| 409 | size(gf[1]); |
---|
| 410 | // the inequalities of the first cone as matrix are: |
---|
| 411 | print(gf[1][1][1]); |
---|
| 412 | // the inequalities of the first cone as string are: |
---|
| 413 | print(gf[1][1][2]); |
---|
| 414 | // the rows of the following matrix are the extreme rays of the first cone: |
---|
| 415 | print(gf[1][1][3]); |
---|
| 416 | // each cone contains the linearity space spanned by: |
---|
| 417 | print(gf[2]); |
---|
| 418 | } |
---|
| 419 | |
---|
| 420 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 421 | |
---|
[7e8485] | 422 | proc groebnerFan (poly f) |
---|
| 423 | "USAGE: groebnerFan(f); f poly |
---|
| 424 | RETURN: list, the ith entry of L[1] contains information about the ith cone |
---|
| 425 | in the Groebner fan dual to the ith vertex in the Newton |
---|
[b0732eb] | 426 | polytope of the f |
---|
[7e8485] | 427 | @* L[1][i][1] = integer matrix representing the inequalities |
---|
| 428 | which describe the cone |
---|
| 429 | @* L[1][i][2] = a list which contains the inequalities represented |
---|
[b0732eb] | 430 | by L[1][i][1] as a list of strings |
---|
[7e8485] | 431 | @* L[1][i][3] = an interger matrix whose rows are the extreme rays |
---|
[b0732eb] | 432 | of the cone |
---|
[7e8485] | 433 | @* L[2] = is an integer matrix whose rows span the linearity space |
---|
| 434 | of the fan, i.e. the linear space which is contained |
---|
| 435 | in each cone |
---|
| 436 | @* L[3] = the Newton polytope of f in the format of the procedure |
---|
[b0732eb] | 437 | newtonPolytope |
---|
[7e8485] | 438 | @* L[4] = integer matrix where each row represents the exponent |
---|
[b0732eb] | 439 | vector of one monomial occuring in the input polynomial |
---|
| 440 | NOTE: - if you have already computed the Newton polytope of f then you might want |
---|
[7e8485] | 441 | to use the procedure normalFan instead in order to avoid doing costly |
---|
[b0732eb] | 442 | computation twice |
---|
| 443 | @* - the procedure calls for its computation polymake by Ewgenij Gawrilow, |
---|
| 444 | TU Berlin and Michael Joswig, so it only works if polymake is installed; |
---|
| 445 | see http://www.math.tu-berlin.de/polymake/ |
---|
| 446 | EXAMPLE: example groebnerFan; shows an example" |
---|
| 447 | { |
---|
| 448 | int i,j; |
---|
[7e8485] | 449 | // compute the list of exponent vectors of the polynomial, which are |
---|
[b0732eb] | 450 | // the lattice points whose convex hull is the Newton polytope of f |
---|
| 451 | intmat exponents[size(f)][nvars(basering)]; |
---|
| 452 | while (f!=0) |
---|
| 453 | { |
---|
| 454 | i++; |
---|
| 455 | exponents[i,1..nvars(basering)]=leadexp(f); |
---|
| 456 | f=f-lead(f); |
---|
| 457 | } |
---|
| 458 | // call polymakePolytope with exponents |
---|
[7e8485] | 459 | list newtonp=polymakePolytope(exponents); |
---|
[b0732eb] | 460 | // get the variables as string |
---|
| 461 | string variablen; |
---|
| 462 | for (i=1;i<=nvars(basering);i++) |
---|
| 463 | { |
---|
| 464 | variablen=variablen+string(var(i))+","; |
---|
| 465 | } |
---|
| 466 | variablen=variablen[1,size(variablen)-1]; |
---|
| 467 | // call normalFan in order to compute the Groebner fan |
---|
| 468 | list gf=normalFan(newtonp[1],newtonp[4],newtonp[3],1,variablen); |
---|
| 469 | // append newtonp to gf |
---|
| 470 | gf[3]=newtonp; |
---|
| 471 | // append the exponent vectors to gf |
---|
| 472 | gf[4]=exponents; |
---|
| 473 | return(gf); |
---|
| 474 | } |
---|
| 475 | example |
---|
| 476 | { |
---|
| 477 | "EXAMPLE:"; |
---|
| 478 | echo=2; |
---|
| 479 | ring r=0,(x,y,z),dp; |
---|
| 480 | matrix M[4][1]=1,x,y,z; |
---|
| 481 | poly f=y3+x2+xy+2xz+yz+z2+1; |
---|
| 482 | // the Newton polytope of f is |
---|
| 483 | list gf=groebnerFan(f); |
---|
| 484 | // the exponent vectors of f are ordered as follows |
---|
| 485 | gf[4]; |
---|
| 486 | // the first cone of the groebner fan has the inequalities |
---|
| 487 | gf[1][1][1]; |
---|
| 488 | // as a string they look like |
---|
| 489 | gf[1][1][2]; |
---|
| 490 | // and it has the extreme rays |
---|
| 491 | print(gf[1][1][3]); |
---|
| 492 | // the linearity space is spanned by |
---|
| 493 | print(gf[2]); |
---|
| 494 | // the vertices of the Newton polytope are: |
---|
| 495 | gf[3][1]; |
---|
| 496 | // its dimension is |
---|
| 497 | gf[3][2]; |
---|
| 498 | // np[3] contains information how the vertices are connected to each other, |
---|
| 499 | // e.g. the 1st vertex is connected to the 2nd, 3rd and 4th vertex |
---|
| 500 | gf[3][3][1]; |
---|
| 501 | } |
---|
| 502 | |
---|
| 503 | |
---|
| 504 | |
---|
| 505 | /////////////////////////////////////////////////////////////////////////////// |
---|
| 506 | /// PROCEDURES USING TOPCOM |
---|
| 507 | /////////////////////////////////////////////////////////////////////////////// |
---|
| 508 | |
---|
[7e8485] | 509 | proc triangulations (list polygon,list #) |
---|
| 510 | "USAGE: triangulations(polygon[,#]); list polygon, list # |
---|
| 511 | ASSUME: polygon is a list of integer vectors of the same size representing |
---|
| 512 | the affine coordinates of the lattice points |
---|
[b0732eb] | 513 | PURPOSE: the procedure considers the marked polytope given as the convex hull of |
---|
| 514 | the lattice points and with these lattice points as markings; it then |
---|
[7e8485] | 515 | computes all possible triangulations of this marked polytope |
---|
[b0732eb] | 516 | RETURN: list, each entry corresponds to one triangulation and the ith entry is |
---|
| 517 | itself a list of integer vectors of size three, where each integer |
---|
| 518 | vector defines one triangle in the triangulation by telling which |
---|
| 519 | points of the input are the vertices of the triangle |
---|
| 520 | NOTE:- the procedure calls for its computations the program points2triangs |
---|
| 521 | from the program topcom by Joerg Rambau, Universitaet Bayreuth; it |
---|
[7e8485] | 522 | therefore is necessary that this program is installed in order to use |
---|
[b0732eb] | 523 | this procedure; see |
---|
| 524 | @* http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM |
---|
[7e8485] | 525 | @* - if you only want to have the regular triangulations the procedure should |
---|
| 526 | be called with the string 'regular' as optional argument |
---|
| 527 | @* - the procedure creates the files /tmp/triangulationsinput and |
---|
[b0732eb] | 528 | /tmp/triangulationsoutput; |
---|
[7e8485] | 529 | the former is used as input for points2triangs and the latter is its |
---|
| 530 | output containing the triangulations of corresponding to points in the |
---|
| 531 | format of points2triangs; if you wish to use this for further |
---|
| 532 | computations with topcom, you have to call the procedure with the |
---|
| 533 | string 'keepfiles' as optional argument |
---|
| 534 | @* - note that an integer i in an integer vector representing a triangle |
---|
| 535 | refers to the ith lattice point, i.e. polygon[i]; this convention is |
---|
| 536 | different from TOPCOM's convention, where i would refer to the i-1st |
---|
[b0732eb] | 537 | lattice point |
---|
| 538 | EXAMPLE: example triangulations; shows an example" |
---|
| 539 | { |
---|
| 540 | int i,j; |
---|
[7e8485] | 541 | // check for optional arguments |
---|
| 542 | int regular,keepfiles; |
---|
| 543 | if (size(#)>0) |
---|
| 544 | { |
---|
| 545 | for (i=1;i<=size(#);i++) |
---|
| 546 | { |
---|
| 547 | if (typeof(#[i])=="string") |
---|
| 548 | { |
---|
| 549 | if (#[i]=="keepfiles") |
---|
| 550 | { |
---|
| 551 | keepfiles=1; |
---|
| 552 | } |
---|
| 553 | if (#[i]=="regular") |
---|
| 554 | { |
---|
| 555 | regular=1; |
---|
| 556 | } |
---|
| 557 | } |
---|
| 558 | } |
---|
| 559 | } |
---|
| 560 | // prepare the input for points2triangs by writing the input polygon in the |
---|
[b0732eb] | 561 | // necessary format |
---|
| 562 | string spi="["; |
---|
| 563 | for (i=1;i<=size(polygon);i++) |
---|
| 564 | { |
---|
| 565 | polygon[i][size(polygon[i])+1]=1; |
---|
| 566 | spi=spi+"["+string(polygon[i])+"]"; |
---|
| 567 | if (i<size(polygon)) |
---|
| 568 | { |
---|
| 569 | spi=spi+","; |
---|
| 570 | } |
---|
| 571 | } |
---|
| 572 | spi=spi+"]"; |
---|
| 573 | write(":w /tmp/triangulationsinput",spi); |
---|
| 574 | // call points2triangs |
---|
[7e8485] | 575 | if (regular==1) // compute only regular triangulations |
---|
| 576 | { |
---|
| 577 | system("sh","cd /tmp; points2triangs --regular < triangulationsinput > triangulationsoutput"); |
---|
| 578 | } |
---|
| 579 | else // compute all triangulations |
---|
| 580 | { |
---|
| 581 | system("sh","cd /tmp; points2triangs < triangulationsinput > triangulationsoutput"); |
---|
| 582 | } |
---|
[b0732eb] | 583 | string p2t=read("/tmp/triangulationsoutput"); // takes result of points2triangs |
---|
[7e8485] | 584 | // delete the tmp-files, if no second argument is given |
---|
| 585 | if (keepfiles==0) |
---|
[b0732eb] | 586 | { |
---|
| 587 | system("sh","cd /tmp; rm -f triangulationsinput; rm -f triangulationsoutput"); |
---|
| 588 | } |
---|
[7e8485] | 589 | // preprocessing of p2t if points2triangs is version >= 0.15 |
---|
[b0732eb] | 590 | // brings p2t to the format of version 0.14 |
---|
| 591 | string np2t; // takes the triangulations in Singular format |
---|
| 592 | for (i=1;i<=size(p2t)-2;i++) |
---|
| 593 | { |
---|
| 594 | if ((p2t[i]==":") and (p2t[i+1]=="=") and (p2t[i+2]=="[")) |
---|
| 595 | { |
---|
| 596 | np2t=np2t+p2t[i]+p2t[i+1]; |
---|
| 597 | i=i+3; |
---|
| 598 | while (p2t[i]!=":") |
---|
| 599 | { |
---|
| 600 | i=i+1; |
---|
| 601 | } |
---|
| 602 | } |
---|
| 603 | else |
---|
| 604 | { |
---|
| 605 | if ((p2t[i]=="]") and (p2t[i+1]==";")) |
---|
| 606 | { |
---|
| 607 | np2t=np2t+p2t[i+1]; |
---|
| 608 | i=i+1; |
---|
| 609 | } |
---|
| 610 | else |
---|
[7e8485] | 611 | { |
---|
[b0732eb] | 612 | np2t=np2t+p2t[i]; |
---|
| 613 | } |
---|
| 614 | } |
---|
| 615 | } |
---|
| 616 | if (p2t[size(p2t)-1]=="]") |
---|
| 617 | { |
---|
| 618 | np2t=np2t+p2t[size(p2t)]; |
---|
| 619 | } |
---|
| 620 | else |
---|
| 621 | { |
---|
| 622 | if (np2t[size(np2t)]!=";") |
---|
[7e8485] | 623 | { |
---|
[b0732eb] | 624 | np2t=np2t+p2t[size(p2t)-1]+p2t[size(p2t)]; |
---|
| 625 | } |
---|
| 626 | } |
---|
| 627 | p2t=np2t; |
---|
| 628 | np2t=""; |
---|
| 629 | // transform the points2triangs output of version 0.14 into Singular format |
---|
| 630 | for (i=1;i<=size(p2t);i++) |
---|
| 631 | { |
---|
| 632 | if (p2t[i]=="=") |
---|
| 633 | { |
---|
| 634 | np2t=np2t+p2t[i]+"list("; |
---|
| 635 | i++; |
---|
| 636 | } |
---|
| 637 | else |
---|
| 638 | { |
---|
| 639 | if (p2t[i]!=":") |
---|
| 640 | { |
---|
| 641 | if ((p2t[i]=="}") and (p2t[i+1]=="}")) |
---|
| 642 | { |
---|
| 643 | np2t=np2t+"))"; |
---|
| 644 | i++; |
---|
[7e8485] | 645 | } |
---|
[b0732eb] | 646 | else |
---|
| 647 | { |
---|
| 648 | if (p2t[i]=="{") |
---|
| 649 | { |
---|
| 650 | np2t=np2t+"intvec("; |
---|
| 651 | } |
---|
| 652 | else |
---|
| 653 | { |
---|
| 654 | if (p2t[i]=="}") |
---|
| 655 | { |
---|
| 656 | np2t=np2t+")"; |
---|
| 657 | } |
---|
| 658 | else |
---|
| 659 | { |
---|
[7e8485] | 660 | if (p2t[i]=="[") |
---|
| 661 | { |
---|
| 662 | // in Topcom version 17.4 (and maybe also in earlier versions) the list |
---|
| 663 | // of triangulations is indexed starting with index 0, in Singular |
---|
| 664 | // we have to start with index 1 |
---|
| 665 | np2t=np2t+p2t[i]+"1+"; |
---|
| 666 | } |
---|
| 667 | else |
---|
| 668 | { |
---|
| 669 | np2t=np2t+p2t[i]; |
---|
| 670 | } |
---|
[b0732eb] | 671 | } |
---|
| 672 | } |
---|
| 673 | } |
---|
| 674 | } |
---|
| 675 | } |
---|
| 676 | } |
---|
| 677 | list T; |
---|
| 678 | execute(np2t); |
---|
[7e8485] | 679 | // depending on the version of Topcom, the list T has or has not an entry T[1] |
---|
| 680 | // if it has none, the entry should be removed |
---|
| 681 | while (typeof(T[1])=="none") |
---|
| 682 | { |
---|
| 683 | T=delete(T,1); |
---|
| 684 | } |
---|
[b0732eb] | 685 | // raise each index by one |
---|
| 686 | for (i=1;i<=size(T);i++) |
---|
| 687 | { |
---|
| 688 | for (j=1;j<=size(T[i]);j++) |
---|
| 689 | { |
---|
| 690 | T[i][j]=T[i][j]+1; |
---|
| 691 | } |
---|
| 692 | } |
---|
| 693 | return(T); |
---|
| 694 | } |
---|
| 695 | example |
---|
| 696 | { |
---|
| 697 | "EXAMPLE:"; |
---|
| 698 | echo=2; |
---|
[7e8485] | 699 | // the lattice points of the unit square in the plane |
---|
[b0732eb] | 700 | list polygon=intvec(0,0),intvec(0,1),intvec(1,0),intvec(1,1); |
---|
| 701 | // the triangulations of this lattice point configuration are computed |
---|
| 702 | list triang=triangulations(polygon); |
---|
| 703 | triang; |
---|
| 704 | } |
---|
| 705 | |
---|
| 706 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 707 | |
---|
| 708 | proc secondaryPolytope (list polygon,list #) |
---|
| 709 | "USAGE: secondaryPolytope(polygon[,#]); list polygon, list # |
---|
[7e8485] | 710 | ASSUME: - polygon is a list of integer vectors of the same size representing |
---|
[b0732eb] | 711 | the affine coordinates of lattice points |
---|
[7e8485] | 712 | @* - if the triangulations of the corresponding polygon have already been |
---|
[b0732eb] | 713 | computed with the procedure triangulations then these can be given as |
---|
| 714 | a second (optional) argument in order to avoid doing this computation |
---|
| 715 | again |
---|
| 716 | PURPOSE: the procedure considers the marked polytope given as the convex hull of |
---|
| 717 | the lattice points and with these lattice points as markings; it then |
---|
[7e8485] | 718 | computes the lattice points of the secondary polytope given by this |
---|
[b0732eb] | 719 | marked polytope which correspond to the triangulations computed by |
---|
| 720 | the procedure triangulations |
---|
| 721 | RETURN: list, say L, such that: |
---|
| 722 | @* L[1] = intmat, each row gives the affine coordinates of a lattice |
---|
[7e8485] | 723 | point in the secondary polytope given by the marked |
---|
| 724 | polytope corresponding to polygon |
---|
[b0732eb] | 725 | @* L[2] = the list of corresponding triangulations |
---|
[7e8485] | 726 | NOTE: if the triangluations are not handed over as optional argument the |
---|
[b0732eb] | 727 | procedure calls for its computation of these triangulations the program |
---|
[7e8485] | 728 | points2triangs from the program topcom by Joerg Rambau, Universitaet |
---|
| 729 | Bayreuth; it therefore is necessary that this program is installed in |
---|
[b0732eb] | 730 | order to use this procedure; see |
---|
| 731 | @* http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM |
---|
| 732 | EXAMPLE: example secondaryPolytope; shows an example" |
---|
| 733 | { |
---|
| 734 | // compute the triangulations of the point configuration with points2triangs |
---|
| 735 | if (size(#)==0) |
---|
| 736 | { |
---|
| 737 | list triangs=triangulations(polygon); |
---|
| 738 | } |
---|
| 739 | else |
---|
| 740 | { |
---|
| 741 | list triangs=#; |
---|
| 742 | } |
---|
| 743 | int i,j,k,l; |
---|
| 744 | intmat N[2][2]; // is used to compute areas of triangles |
---|
[7e8485] | 745 | intvec vertex; // stores a point in the secondary polytope as |
---|
[b0732eb] | 746 | // intermediate result |
---|
| 747 | int eintrag; |
---|
| 748 | int halt; |
---|
[7e8485] | 749 | intmat secpoly[size(triangs)][size(polygon)]; // stores all lattice points |
---|
[b0732eb] | 750 | // of the secondary polytope |
---|
[7e8485] | 751 | // consider each triangulation and compute the corresponding point |
---|
[b0732eb] | 752 | // in the secondary polytope |
---|
| 753 | for (i=1;i<=size(triangs);i++) |
---|
| 754 | { |
---|
[7e8485] | 755 | // for each triangulation we have to compute the coordinates |
---|
[b0732eb] | 756 | // corresponding to each marked point |
---|
| 757 | for (j=1;j<=size(polygon);j++) |
---|
| 758 | { |
---|
| 759 | eintrag=0; |
---|
[7e8485] | 760 | // for each marked point we have to consider all triangles in the |
---|
[b0732eb] | 761 | // triangulation which involve this particular point |
---|
| 762 | for (k=1;k<=size(triangs[i]);k++) |
---|
| 763 | { |
---|
| 764 | halt=0; |
---|
| 765 | for (l=1;(l<=3) and (halt==0);l++) |
---|
| 766 | { |
---|
| 767 | if (triangs[i][k][l]==j) |
---|
| 768 | { |
---|
| 769 | halt=1; |
---|
| 770 | N[1,1]=polygon[triangs[i][k][3]][1]-polygon[triangs[i][k][1]][1]; |
---|
| 771 | N[1,2]=polygon[triangs[i][k][2]][1]-polygon[triangs[i][k][1]][1]; |
---|
| 772 | N[2,1]=polygon[triangs[i][k][3]][2]-polygon[triangs[i][k][1]][2]; |
---|
| 773 | N[2,2]=polygon[triangs[i][k][2]][2]-polygon[triangs[i][k][1]][2]; |
---|
| 774 | eintrag=eintrag+abs(det(N)); |
---|
| 775 | } |
---|
| 776 | } |
---|
| 777 | } |
---|
| 778 | vertex[j]=eintrag; |
---|
| 779 | } |
---|
| 780 | secpoly[i,1..size(polygon)]=vertex; |
---|
| 781 | } |
---|
[7e8485] | 782 | return(list(secpoly,triangs)); |
---|
[b0732eb] | 783 | } |
---|
| 784 | example |
---|
| 785 | { |
---|
| 786 | "EXAMPLE:"; |
---|
| 787 | echo=2; |
---|
| 788 | // the lattice points of the unit square in the plane |
---|
| 789 | list polygon=intvec(0,0),intvec(0,1),intvec(1,0),intvec(1,1); |
---|
| 790 | // the secondary polytope of this lattice point configuration is computed |
---|
| 791 | list secpoly=secondaryPolytope(polygon); |
---|
| 792 | // the points in the secondary polytope |
---|
| 793 | print(secpoly[1]); |
---|
| 794 | // the corresponding triangulations |
---|
| 795 | secpoly[2]; |
---|
| 796 | } |
---|
| 797 | |
---|
| 798 | /////////////////////////////////////////////////////////////////////////////// |
---|
| 799 | /// PROCEDURES USING POLYMAKE AND TOPCOM |
---|
| 800 | /////////////////////////////////////////////////////////////////////////////// |
---|
| 801 | |
---|
| 802 | proc secondaryFan (list polygon,list #) |
---|
| 803 | "USAGE: secondaryFan(polygon[,#]); list polygon, list # |
---|
[7e8485] | 804 | ASSUME: - polygon is a list of integer vectors of the same size representing |
---|
[b0732eb] | 805 | the affine coordinates of lattice points |
---|
[7e8485] | 806 | @* - if the triangulations of the corresponding polygon have already been |
---|
| 807 | computed with the procedure triangulations then these can be given |
---|
| 808 | as a second (optional) argument in order to avoid doing this |
---|
[b0732eb] | 809 | computation again |
---|
| 810 | PURPOSE: the procedure considers the marked polytope given as the convex hull of |
---|
| 811 | the lattice points and with these lattice points as markings; it then |
---|
[7e8485] | 812 | computes the lattice points of the secondary polytope given by this |
---|
[b0732eb] | 813 | marked polytope which correspond to the triangulations computed by |
---|
| 814 | the procedure triangulations |
---|
[7e8485] | 815 | RETURN: list, the ith entry of L[1] contains information about the ith cone in |
---|
| 816 | the secondary fan of the polygon, i.e. the cone dual to the |
---|
[b0732eb] | 817 | ith vertex of the secondary polytope |
---|
[7e8485] | 818 | @* L[1][i][1] = integer matrix representing the inequalities which |
---|
[b0732eb] | 819 | describe the cone dual to the ith vertex |
---|
[7e8485] | 820 | @* L[1][i][2] = a list which contains the inequalities represented |
---|
[b0732eb] | 821 | by L[1][i][1] as a list of strings, where we use the |
---|
| 822 | variables x(1),...,x(n) |
---|
| 823 | @* L[1][i][3] = only present if 'er' is set to 1; in that case it is |
---|
[7e8485] | 824 | an interger matrix whose rows are the extreme rays |
---|
[b0732eb] | 825 | of the cone |
---|
[7e8485] | 826 | @* L[2] = is an integer matrix whose rows span the linearity space |
---|
| 827 | of the fan, i.e. the linear space which is contained in |
---|
[b0732eb] | 828 | each cone |
---|
[7e8485] | 829 | @* L[3] = the secondary polytope in the format of the procedure |
---|
[b0732eb] | 830 | polymakePolytope |
---|
[7e8485] | 831 | @* L[4] = the list of triangulations corresponding to the vertices |
---|
[b0732eb] | 832 | of the secondary polytope |
---|
| 833 | NOTE:- the procedure calls for its computation polymake by Ewgenij Gawrilow, |
---|
| 834 | TU Berlin and Michael Joswig, so it only works if polymake is installed; |
---|
| 835 | see http://www.math.tu-berlin.de/polymake/ |
---|
[7e8485] | 836 | @* - in the optional argument # it is possible to hand over other names for |
---|
| 837 | the variables to be used -- be careful, the format must be correct and |
---|
| 838 | that is not tested, e.g. if you want the variable names to be |
---|
[b0732eb] | 839 | u00,u10,u01,u11 then you must hand over the string 'u11,u10,u01,u11' |
---|
[7e8485] | 840 | @* - if the triangluations are not handed over as optional argument the |
---|
| 841 | procedure calls for its computation of these triangulations the program |
---|
| 842 | points2triangs from the program topcom by Joerg Rambau, Universitaet |
---|
| 843 | Bayreuth; it therefore is necessary that this program is installed in |
---|
[b0732eb] | 844 | order to use this procedure; see |
---|
| 845 | @* http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM |
---|
| 846 | EXAMPLE: example secondaryFan; shows an example" |
---|
| 847 | { |
---|
| 848 | if (size(#)==0) |
---|
| 849 | { |
---|
| 850 | list triang=triangulations(polygon); |
---|
| 851 | } |
---|
| 852 | else |
---|
| 853 | { |
---|
| 854 | list triang=#[1]; |
---|
[7e8485] | 855 | } |
---|
[b0732eb] | 856 | list sp=secondaryPolytope(polygon,triang); |
---|
| 857 | list spp=polymakePolytope(sp[1]); |
---|
| 858 | list sf=normalFan(spp[1],spp[4],spp[3],1); |
---|
| 859 | return(list(sf[1],sf[2],spp,triang)); |
---|
| 860 | } |
---|
| 861 | example |
---|
| 862 | { |
---|
| 863 | "EXAMPLE:"; |
---|
| 864 | echo=2; |
---|
| 865 | // the lattice points of the unit square in the plane |
---|
| 866 | list polygon=intvec(0,0),intvec(0,1),intvec(1,0),intvec(1,1); |
---|
| 867 | // the secondary polytope of this lattice point configuration is computed |
---|
| 868 | list secfan=secondaryFan(polygon); |
---|
| 869 | // the number of cones in the secondary fan of the polygon |
---|
| 870 | size(secfan[1]); |
---|
| 871 | // the inequalities of the first cone as matrix are: |
---|
| 872 | print(secfan[1][1][1]); |
---|
| 873 | // the inequalities of the first cone as string are: |
---|
| 874 | print(secfan[1][1][2]); |
---|
| 875 | // the rows of the following matrix are the extreme rays of the first cone: |
---|
| 876 | print(secfan[1][1][3]); |
---|
| 877 | // each cone contains the linearity space spanned by: |
---|
| 878 | print(secfan[2]); |
---|
| 879 | // the points in the secondary polytope |
---|
| 880 | print(secfan[3][1]); |
---|
| 881 | // the corresponding triangulations |
---|
| 882 | secfan[4]; |
---|
| 883 | } |
---|
| 884 | |
---|
| 885 | |
---|
| 886 | //////////////////////////////////////////////////////////////////////////////// |
---|
| 887 | /// PROCEDURES CONCERNED WITH PLANAR POLYGONS |
---|
| 888 | //////////////////////////////////////////////////////////////////////////////// |
---|
| 889 | |
---|
| 890 | proc cycleLength (list boundary,intvec interior) |
---|
| 891 | "USAGE: cycleLength(boundary,interior); list boundary, intvec interior |
---|
[7e8485] | 892 | ASSUME: boundary is a list of integer vectors describing a cycle in some |
---|
| 893 | convex lattice polygon around the lattice point interior ordered |
---|
[b0732eb] | 894 | clock wise |
---|
| 895 | RETURN: string, the cycle length of the corresponding cycle in the dual |
---|
| 896 | tropical curve |
---|
| 897 | EXAMPLE: example cycleLength; shows an example" |
---|
| 898 | { |
---|
| 899 | int j; |
---|
[7e8485] | 900 | // create a ring whose variables are indexed by the points in |
---|
[b0732eb] | 901 | // boundary resp. by interior |
---|
| 902 | string rst="ring cyclering=0,(u"+string(interior[1])+string(interior[2]); |
---|
| 903 | for (j=1;j<=size(boundary);j++) |
---|
| 904 | { |
---|
| 905 | rst=rst+",u"+string(boundary[j][1])+string(boundary[j][2]); |
---|
| 906 | } |
---|
| 907 | rst=rst+"),lp;"; |
---|
| 908 | execute(rst); |
---|
| 909 | // add the first and second point at the end of boundary |
---|
| 910 | boundary[size(boundary)+1]=boundary[1]; |
---|
| 911 | boundary[size(boundary)+1]=boundary[2]; |
---|
| 912 | poly cl,summand; // takes the cycle length |
---|
| 913 | matrix N1[2][2]; // used to compute the area of a triangle |
---|
| 914 | matrix N2[2][2]; // used to compute the area of a triangle |
---|
| 915 | matrix N3[2][2]; // used to compute the area of a triangle |
---|
| 916 | // for each original point in boundary compute its contribution to the cycle |
---|
| 917 | for (j=2;j<=size(boundary)-1;j++) |
---|
| 918 | { |
---|
| 919 | N1=boundary[j-1]-interior,boundary[j]-interior; |
---|
| 920 | N2=boundary[j]-interior,boundary[j+1]-interior; |
---|
| 921 | N3=boundary[j+1]-interior,boundary[j-1]-interior; |
---|
| 922 | execute("summand=-u"+string(boundary[j][1])+string(boundary[j][2])+"+u"+string(interior[1])+string(interior[2])+";"); |
---|
| 923 | summand=summand*(det(N1)+det(N2)+det(N3))/(det(N1)*det(N2)); |
---|
| 924 | cl=cl+summand; |
---|
| 925 | } |
---|
| 926 | return(string(cl)); |
---|
| 927 | } |
---|
| 928 | example |
---|
| 929 | { |
---|
| 930 | "EXAMPLE:"; |
---|
| 931 | echo=2; |
---|
| 932 | // the integer vectors in boundary are lattice points on the boundary |
---|
| 933 | // of a convex lattice polygon in the plane |
---|
| 934 | list boundary=intvec(0,0),intvec(0,1),intvec(0,2),intvec(2,2), |
---|
| 935 | intvec(2,1),intvec(2,0); |
---|
| 936 | // interior is a lattice point in the interior of this lattice polygon |
---|
| 937 | intvec interior=1,1; |
---|
[7e8485] | 938 | // compute the general cycle length of a cycle of the corresponding cycle |
---|
[b0732eb] | 939 | // in the dual tropical curve, note that (0,1) and (2,1) do not contribute |
---|
| 940 | cycleLength(boundary,interior); |
---|
| 941 | } |
---|
| 942 | |
---|
| 943 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 944 | |
---|
| 945 | proc splitPolygon (list markings) |
---|
| 946 | "USAGE: splitPolygon (markings); markings list |
---|
[7e8485] | 947 | ASSUME: markings is a list of integer vectors representing lattice points in |
---|
| 948 | the plane which we consider as the marked points of the convex lattice |
---|
[b0732eb] | 949 | polytope spanned by them |
---|
[7e8485] | 950 | PURPOSE: split the marked points in the vertices, the points on the facets |
---|
[b0732eb] | 951 | which are not vertices, and the interior points |
---|
| 952 | RETURN: list, L consisting of three lists |
---|
| 953 | @* L[1] : represents the vertices the polygon ordered clockwise |
---|
| 954 | @* L[1][i][1] = intvec, the coordinates of the ith vertex |
---|
| 955 | @* L[1][i][2] = int, the position of L[1][i][1] in markings |
---|
[7e8485] | 956 | @* L[2][i] : represents the lattice points on the facet of the |
---|
| 957 | polygon with endpoints L[1][i] and L[1][i+1] |
---|
[b0732eb] | 958 | (i considered modulo size(L[1])) |
---|
[7e8485] | 959 | @* L[2][i][j][1] = intvec, the coordinates of the jth |
---|
[b0732eb] | 960 | lattice point on that facet |
---|
[7e8485] | 961 | @* L[2][i][j][2] = int, the position of L[2][i][j][1] |
---|
[b0732eb] | 962 | in markings |
---|
[7e8485] | 963 | @* L[3] : represents the interior lattice points of the polygon |
---|
[b0732eb] | 964 | @* L[3][i][1] = intvec, coordinates of ith interior point |
---|
| 965 | @* L[3][i][2] = int, the position of L[3][i][1] in markings |
---|
| 966 | EXAMPLE: example splitPolygon; shows an example" |
---|
| 967 | { |
---|
| 968 | list vert; // stores the result |
---|
| 969 | // compute the boundary of the polygon in an oriented way |
---|
| 970 | list pb=findOrientedBoundary(markings); |
---|
| 971 | // the vertices are just the second entry of pb |
---|
| 972 | vert[1]=pb[2]; |
---|
| 973 | int i,j,k; // indices |
---|
[7e8485] | 974 | list boundary; // stores the points on the facets of the |
---|
[b0732eb] | 975 | // polygon which are not vertices |
---|
[7e8485] | 976 | // append to the boundary points as well as to the vertices |
---|
[b0732eb] | 977 | // the first vertex a second time |
---|
| 978 | pb[1]=pb[1]+list(pb[1][1]); |
---|
| 979 | pb[2]=pb[2]+list(pb[2][1]); |
---|
| 980 | // for each vertex find all points on the facet of the polygon with this vertex |
---|
| 981 | // and the next vertex as endpoints |
---|
| 982 | int z=2; |
---|
| 983 | for (i=1;i<=size(vert[1]);i++) |
---|
| 984 | { |
---|
| 985 | j=1; |
---|
| 986 | list facet; // stores the points on this facet which are not vertices |
---|
| 987 | // while the next vertex is not reached, store the boundary lattice point |
---|
| 988 | while (pb[1][z]!=pb[2][i+1]) |
---|
| 989 | { |
---|
| 990 | facet[j]=pb[1][z]; |
---|
| 991 | j++; |
---|
| 992 | z++; |
---|
| 993 | } |
---|
| 994 | // store the points on the ith facet as boundary[i] |
---|
| 995 | boundary[i]=facet; |
---|
| 996 | kill facet; |
---|
| 997 | z++; |
---|
| 998 | } |
---|
| 999 | // store the information on the boundary in vert[2] |
---|
| 1000 | vert[2]=boundary; |
---|
[7e8485] | 1001 | // find the remaining points in the input which are not on |
---|
[b0732eb] | 1002 | // the boundary by checking |
---|
| 1003 | // for each point in markings if it is contained in pb[1] |
---|
| 1004 | list interior=markings; |
---|
| 1005 | for (i=size(interior);i>=1;i--) |
---|
| 1006 | { |
---|
| 1007 | for (j=1;j<=size(pb[1])-1;j++) |
---|
| 1008 | { |
---|
| 1009 | if (interior[i]==pb[1][j]) |
---|
| 1010 | { |
---|
| 1011 | interior=delete(interior,i); |
---|
| 1012 | j=size(pb[1]); |
---|
| 1013 | } |
---|
| 1014 | } |
---|
| 1015 | } |
---|
| 1016 | // store the interior points in vert[3] |
---|
| 1017 | vert[3]=interior; |
---|
[7e8485] | 1018 | // add to each point in vert the index which it gets from |
---|
[b0732eb] | 1019 | // its position in the input markings; |
---|
| 1020 | // do so for ver[1] |
---|
| 1021 | for (i=1;i<=size(vert[1]);i++) |
---|
| 1022 | { |
---|
| 1023 | j=1; |
---|
| 1024 | while (markings[j]!=vert[1][i]) |
---|
| 1025 | { |
---|
| 1026 | j++; |
---|
| 1027 | } |
---|
| 1028 | vert[1][i]=list(vert[1][i],j); |
---|
| 1029 | } |
---|
| 1030 | // do so for ver[2] |
---|
| 1031 | for (i=1;i<=size(vert[2]);i++) |
---|
| 1032 | { |
---|
| 1033 | for (k=1;k<=size(vert[2][i]);k++) |
---|
| 1034 | { |
---|
| 1035 | j=1; |
---|
| 1036 | while (markings[j]!=vert[2][i][k]) |
---|
| 1037 | { |
---|
| 1038 | j++; |
---|
| 1039 | } |
---|
| 1040 | vert[2][i][k]=list(vert[2][i][k],j); |
---|
| 1041 | } |
---|
| 1042 | } |
---|
| 1043 | // do so for ver[3] |
---|
| 1044 | for (i=1;i<=size(vert[3]);i++) |
---|
| 1045 | { |
---|
| 1046 | j=1; |
---|
| 1047 | while (markings[j]!=vert[3][i]) |
---|
| 1048 | { |
---|
| 1049 | j++; |
---|
| 1050 | } |
---|
| 1051 | vert[3][i]=list(vert[3][i],j); |
---|
[7e8485] | 1052 | } |
---|
[b0732eb] | 1053 | return(vert); |
---|
| 1054 | } |
---|
| 1055 | example |
---|
| 1056 | { |
---|
| 1057 | "EXAMPLE:"; |
---|
| 1058 | echo=2; |
---|
[7e8485] | 1059 | // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) |
---|
[b0732eb] | 1060 | // with all integer points as markings |
---|
| 1061 | list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0), |
---|
| 1062 | intvec(0,0),intvec(2,1),intvec(0,1),intvec(1,2), |
---|
| 1063 | intvec(0,2),intvec(0,3); |
---|
| 1064 | // split the polygon in its vertices, its facets and its interior points |
---|
| 1065 | list sp=splitPolygon(polygon); |
---|
| 1066 | // the vertices |
---|
| 1067 | sp[1]; |
---|
| 1068 | // the points on facets which are not vertices |
---|
| 1069 | sp[2]; |
---|
| 1070 | // the interior points |
---|
| 1071 | sp[3]; |
---|
| 1072 | } |
---|
| 1073 | |
---|
| 1074 | |
---|
| 1075 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 1076 | |
---|
| 1077 | proc eta (list triang,list polygon) |
---|
| 1078 | "USAGE: eta(triang,polygon); triang, polygon list |
---|
[7e8485] | 1079 | ASSUME: polygon has the format of the output of splitPolygon, i.e. it is a |
---|
| 1080 | list with three entries describing a convex lattice polygon in the |
---|
[b0732eb] | 1081 | following way: |
---|
[7e8485] | 1082 | @* polygon[1] : is a list of lists; for each i the entry polygon[1][i][1] |
---|
| 1083 | is a lattice point which is a vertex of the lattice |
---|
[b0732eb] | 1084 | polygon, and polygon[1][i][2] is an integer assigned to |
---|
| 1085 | this lattice point as identifying index |
---|
[7e8485] | 1086 | @* polygon[2] : is a list of lists; for each vertex of the polygon, |
---|
| 1087 | i.e. for each entry in polygon[1], it contains a list |
---|
| 1088 | polygon[2][i], which contains the lattice points on the |
---|
| 1089 | facet with endpoints polygon[1][i] and polygon[1][i+1] |
---|
[b0732eb] | 1090 | - i considered mod size(polygon[1]); |
---|
[7e8485] | 1091 | each such lattice point contributes an entry |
---|
[b0732eb] | 1092 | polygon[2][i][j][1] which is an integer |
---|
[7e8485] | 1093 | vector giving the coordinate of the lattice point and an |
---|
[b0732eb] | 1094 | entry polygon[2][i][j][2] which is the identifying index |
---|
[7e8485] | 1095 | @* polygon[3] : is a list of lists, where each entry corresponds to a |
---|
| 1096 | lattice point in the interior of the polygon, with |
---|
[b0732eb] | 1097 | polygon[3][j][1] being the coordinates of the point |
---|
| 1098 | and polygon[3][j][2] being the identifying index; |
---|
[7e8485] | 1099 | @* triang is a list of integer vectors all of size three describing a |
---|
| 1100 | triangulation of the polygon described by polygon; if an entry of |
---|
| 1101 | triang is the vector (i,j,k) then the triangle is built by the vertices |
---|
[b0732eb] | 1102 | with indices i, j and k |
---|
[7e8485] | 1103 | RETURN: intvec, the integer vector eta describing that vertex of the Newton |
---|
| 1104 | polytope discriminant of the polygone whose dual cone in the |
---|
| 1105 | Groebner fan contains the cone of the secondary fan of the |
---|
[b0732eb] | 1106 | polygon corresponding to the given triangulation |
---|
[7e8485] | 1107 | NOTE: for a better description of eta see Gelfand, Kapranov, |
---|
[b0732eb] | 1108 | Zelevinski: Discriminants, Resultants and multidimensional Determinants. |
---|
| 1109 | Chapter 10. |
---|
| 1110 | EXAMPLE: example eta; shows an example" |
---|
| 1111 | { |
---|
| 1112 | int i,j,k,l,m,n; // index variables |
---|
[7e8485] | 1113 | list ordpolygon; // stores the lattice points in the order |
---|
[b0732eb] | 1114 | // used in the triangulation |
---|
| 1115 | list triangarea; // stores the areas of the triangulations |
---|
| 1116 | intmat N[2][2]; // used to compute triangle areas |
---|
| 1117 | // 1) store the lattice points in the order used in the triangulation |
---|
| 1118 | // go first through all vertices of the polytope |
---|
| 1119 | for (j=1;j<=size(polygon[1]);j++) |
---|
| 1120 | { |
---|
| 1121 | ordpolygon[polygon[1][j][2]]=polygon[1][j][1]; |
---|
| 1122 | } |
---|
| 1123 | // then consider all inner points |
---|
| 1124 | for (j=1;j<=size(polygon[3]);j++) |
---|
| 1125 | { |
---|
| 1126 | ordpolygon[polygon[3][j][2]]=polygon[3][j][1]; |
---|
| 1127 | } |
---|
| 1128 | // finally consider all lattice points on the boundary which are not vertices |
---|
| 1129 | for (j=1;j<=size(polygon[2]);j++) |
---|
| 1130 | { |
---|
| 1131 | for (i=1;i<=size(polygon[2][j]);i++) |
---|
| 1132 | { |
---|
| 1133 | ordpolygon[polygon[2][j][i][2]]=polygon[2][j][i][1]; |
---|
| 1134 | } |
---|
| 1135 | } |
---|
| 1136 | // 2) compute for each triangle in the triangulation the area of the triangle |
---|
| 1137 | for (i=1;i<=size(triang);i++) |
---|
| 1138 | { |
---|
[7e8485] | 1139 | // Note that the ith lattice point in orderedpolygon has the |
---|
[b0732eb] | 1140 | // number i-1 in the triangulation! |
---|
| 1141 | N=ordpolygon[triang[i][1]]-ordpolygon[triang[i][2]],ordpolygon[triang[i][1]]-ordpolygon[triang[i][3]]; |
---|
| 1142 | triangarea[i]=abs(det(N)); |
---|
| 1143 | } |
---|
| 1144 | intvec ETA; // stores the eta_ij |
---|
[7e8485] | 1145 | int etaij; // stores the part of eta_ij during computations |
---|
[b0732eb] | 1146 | // which comes from triangle areas |
---|
[7e8485] | 1147 | int seitenlaenge; // stores the part of eta_ij during computations |
---|
[b0732eb] | 1148 | // which comes from boundary facets |
---|
| 1149 | list seiten; // stores the lattice points on facets of the polygon |
---|
| 1150 | intvec v; // used to compute a facet length |
---|
[7e8485] | 1151 | // 3) store first in seiten[i] all lattice points on the facet |
---|
[b0732eb] | 1152 | // connecting the ith vertex, |
---|
[7e8485] | 1153 | // i.e. polygon[1][i], with the i+1st vertex, i.e. polygon[1][i+1], |
---|
[b0732eb] | 1154 | // where we replace i+1 |
---|
| 1155 | // 1 if i=size(polygon[1]); |
---|
[7e8485] | 1156 | // then append the last entry of seiten once more at the very |
---|
[b0732eb] | 1157 | // beginning of seiten, so |
---|
| 1158 | // that the index is shifted by one |
---|
| 1159 | for (i=1;i<=size(polygon[1]);i++) |
---|
| 1160 | { |
---|
| 1161 | if (i<size(polygon[1])) |
---|
| 1162 | { |
---|
| 1163 | seiten[i]=list(polygon[1][i])+polygon[2][i]+list(polygon[1][i+1]); |
---|
| 1164 | } |
---|
| 1165 | else |
---|
| 1166 | { |
---|
| 1167 | seiten[i]=list(polygon[1][i])+polygon[2][i]+list(polygon[1][1]); |
---|
| 1168 | } |
---|
| 1169 | } |
---|
| 1170 | seiten=insert(seiten,seiten[size(seiten)],0); |
---|
| 1171 | // 4) compute the eta_ij for all vertices of the polygon |
---|
| 1172 | for (j=1;j<=size(polygon[1]);j++) |
---|
| 1173 | { |
---|
| 1174 | // the vertex itself contributes a 1 |
---|
| 1175 | etaij=1; |
---|
| 1176 | // check for each triangle in the triangulation ... |
---|
| 1177 | for (k=1;k<=size(triang);k++) |
---|
| 1178 | { |
---|
| 1179 | // ... if the vertex is actually a vertex of the triangle ... |
---|
| 1180 | if ((polygon[1][j][2]==triang[k][1]) or (polygon[1][j][2]==triang[k][2]) or (polygon[1][j][2]==triang[k][3])) |
---|
| 1181 | { |
---|
[7e8485] | 1182 | // ... if so, add the area of the triangle to etaij |
---|
[b0732eb] | 1183 | etaij=etaij+triangarea[k]; |
---|
[7e8485] | 1184 | // then check if that triangle has a facet which is contained |
---|
| 1185 | // in one of the |
---|
[b0732eb] | 1186 | // two facets of the polygon which are adjecent to the given vertex ... |
---|
| 1187 | // these two facets are seiten[j] and seiten[j+1] |
---|
| 1188 | for (n=j;n<=j+1;n++) |
---|
| 1189 | { |
---|
| 1190 | // check for each lattice point in the facet of the polygon ... |
---|
| 1191 | for (l=1;l<=size(seiten[n]);l++) |
---|
| 1192 | { |
---|
| 1193 | // ... and for each lattice point in the triangle ... |
---|
| 1194 | for (m=1;m<=size(triang[k]);m++) |
---|
| 1195 | { |
---|
| 1196 | // ... if they coincide and are not the vertex itself ... |
---|
| 1197 | if ((seiten[n][l][2]==triang[k][m]) and (seiten[n][l][2]!=polygon[1][j][2])) |
---|
| 1198 | { |
---|
[7e8485] | 1199 | // if so, then compute the vector pointing from this |
---|
[b0732eb] | 1200 | // lattice point to the vertex |
---|
| 1201 | v=polygon[1][j][1]-seiten[n][l][1]; |
---|
[7e8485] | 1202 | // and the lattice length of this vector has to be |
---|
[b0732eb] | 1203 | // subtracted from etaij |
---|
| 1204 | etaij=etaij-abs(gcd(v[1],v[2])); |
---|
| 1205 | } |
---|
| 1206 | } |
---|
| 1207 | } |
---|
| 1208 | } |
---|
| 1209 | } |
---|
| 1210 | } |
---|
| 1211 | // store etaij in the list |
---|
| 1212 | ETA[polygon[1][j][2]]=etaij; |
---|
| 1213 | } |
---|
[7e8485] | 1214 | // 5) compute the eta_ij for all lattice points on the facets |
---|
[b0732eb] | 1215 | // of the polygon which are not vertices, these are the |
---|
| 1216 | // lattice points in polygon[2][1] to polygon[2][size(polygon[1])] |
---|
| 1217 | for (i=1;i<=size(polygon[2]);i++) |
---|
| 1218 | { |
---|
| 1219 | for (j=1;j<=size(polygon[2][i]);j++) |
---|
[7e8485] | 1220 | { |
---|
[b0732eb] | 1221 | // initialise etaij |
---|
| 1222 | etaij=0; |
---|
| 1223 | // initialise seitenlaenge |
---|
| 1224 | seitenlaenge=0; |
---|
| 1225 | // check for each triangle in the triangulation ... |
---|
| 1226 | for (k=1;k<=size(triang);k++) |
---|
| 1227 | { |
---|
| 1228 | // ... if the vertex is actually a vertex of the triangle ... |
---|
| 1229 | 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])) |
---|
| 1230 | { |
---|
[7e8485] | 1231 | // ... if so, add the area of the triangle to etaij |
---|
[b0732eb] | 1232 | etaij=etaij+triangarea[k]; |
---|
[7e8485] | 1233 | // then check if that triangle has a facet which is contained in the |
---|
[b0732eb] | 1234 | // facet of the polygon which contains the lattice point in question, |
---|
| 1235 | // this is the facet seiten[i+1]; |
---|
| 1236 | // check for each lattice point in the facet of the polygon ... |
---|
| 1237 | for (l=1;l<=size(seiten[i+1]);l++) |
---|
| 1238 | { |
---|
| 1239 | // ... and for each lattice point in the triangle ... |
---|
| 1240 | for (m=1;m<=size(triang[k]);m++) |
---|
[7e8485] | 1241 | { |
---|
[b0732eb] | 1242 | // ... if they coincide and are not the vertex itself ... |
---|
| 1243 | if ((seiten[i+1][l][2]==triang[k][m]) and (seiten[i+1][l][2]!=polygon[2][i][j][2])) |
---|
| 1244 | { |
---|
[7e8485] | 1245 | // if so, then compute the vector pointing from |
---|
[b0732eb] | 1246 | // this lattice point to the vertex |
---|
| 1247 | v=polygon[2][i][j][1]-seiten[i+1][l][1]; |
---|
[7e8485] | 1248 | // and the lattice length of this vector contributes |
---|
[b0732eb] | 1249 | // to seitenlaenge |
---|
| 1250 | seitenlaenge=seitenlaenge+abs(gcd(v[1],v[2])); |
---|
| 1251 | } |
---|
| 1252 | } |
---|
| 1253 | } |
---|
| 1254 | } |
---|
| 1255 | } |
---|
[7e8485] | 1256 | // if the lattice point was a vertex of any triangle |
---|
[b0732eb] | 1257 | // in the triangulation ... |
---|
| 1258 | if (etaij!=0) |
---|
| 1259 | { |
---|
| 1260 | // then eta_ij is the sum of the triangle areas minus seitenlaenge |
---|
| 1261 | ETA[polygon[2][i][j][2]]=etaij-seitenlaenge; |
---|
| 1262 | } |
---|
| 1263 | else |
---|
| 1264 | { |
---|
| 1265 | // otherwise it is just zero |
---|
| 1266 | ETA[polygon[2][i][j][2]]=0; |
---|
| 1267 | } |
---|
| 1268 | } |
---|
| 1269 | } |
---|
| 1270 | // 4) compute the eta_ij for all inner lattice points of the polygon |
---|
| 1271 | for (j=1;j<=size(polygon[3]);j++) |
---|
| 1272 | { |
---|
| 1273 | // initialise etaij |
---|
| 1274 | etaij=0; |
---|
| 1275 | // check for each triangle in the triangulation ... |
---|
| 1276 | for (k=1;k<=size(triang);k++) |
---|
| 1277 | { |
---|
| 1278 | // ... if the vertex is actually a vertex of the triangle ... |
---|
| 1279 | if ((polygon[3][j][2]==triang[k][1]) or (polygon[3][j][2]==triang[k][2]) or (polygon[3][j][2]==triang[k][3])) |
---|
| 1280 | { |
---|
[7e8485] | 1281 | // ... if so, add the area of the triangle to etaij |
---|
[b0732eb] | 1282 | etaij=etaij+triangarea[k]; |
---|
| 1283 | } |
---|
| 1284 | } |
---|
| 1285 | // store etaij in ETA |
---|
| 1286 | ETA[polygon[3][j][2]]=etaij; |
---|
| 1287 | } |
---|
| 1288 | return(ETA); |
---|
| 1289 | } |
---|
| 1290 | example |
---|
| 1291 | { |
---|
| 1292 | "EXAMPLE:"; |
---|
| 1293 | echo=2; |
---|
[7e8485] | 1294 | // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) |
---|
[b0732eb] | 1295 | // with all integer points as markings |
---|
| 1296 | list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0), |
---|
| 1297 | intvec(0,0),intvec(2,1),intvec(0,1),intvec(1,2), |
---|
| 1298 | intvec(0,2),intvec(0,3); |
---|
| 1299 | // split the polygon in its vertices, its facets and its interior points |
---|
| 1300 | list sp=splitPolygon(polygon); |
---|
[7e8485] | 1301 | // define a triangulation by connecting the only interior point |
---|
[b0732eb] | 1302 | // with the vertices |
---|
| 1303 | list triang=intvec(1,2,5),intvec(1,5,10),intvec(1,5,10); |
---|
| 1304 | // compute the eta-vector of this triangulation |
---|
| 1305 | eta(triang,sp); |
---|
| 1306 | } |
---|
[7e8485] | 1307 | |
---|
[b0732eb] | 1308 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 1309 | |
---|
| 1310 | proc findOrientedBoundary (list polygon) |
---|
| 1311 | "USAGE: findOrientedBoundary(polygon); polygon list |
---|
[7e8485] | 1312 | ASSUME: polygon is a list of integer vectors defining integer lattice points |
---|
[b0732eb] | 1313 | in the plane |
---|
| 1314 | RETURN: list l with the following interpretation |
---|
[7e8485] | 1315 | @* l[1] = list of integer vectors such that the polygonal path |
---|
| 1316 | defined by these is the boundary of the convex hull of |
---|
[b0732eb] | 1317 | the lattice points in polygon |
---|
| 1318 | @* l[2] = list, the redundant points in l[1] have been removed |
---|
| 1319 | EXAMPLE: example findOrientedBoundary; shows an example" |
---|
| 1320 | { |
---|
| 1321 | // Order the vertices such that passing from one to the next we travel along |
---|
| 1322 | // the boundary of the convex hull of the vertices clock wise |
---|
| 1323 | int d,k,i,j; |
---|
| 1324 | intmat D[2][2]; |
---|
| 1325 | ///////////////////////////////////// |
---|
| 1326 | // Treat first the pathological cases that the polygon is not two-dimensional: |
---|
| 1327 | ///////////////////////////////////// |
---|
| 1328 | // if the polygon is empty or only one point or a line segment of two points |
---|
| 1329 | if (size(polygon)<=2) |
---|
| 1330 | { |
---|
| 1331 | return(list(polygon,polygon)); |
---|
| 1332 | } |
---|
| 1333 | // check is the polygon is only a line segment given by more than two points; |
---|
[7e8485] | 1334 | // for this first compute sum of the absolute values of the determinants |
---|
[b0732eb] | 1335 | // of the matrices whose |
---|
[7e8485] | 1336 | // rows are the vectors pointing from the first to the second point |
---|
[b0732eb] | 1337 | // and from the |
---|
[7e8485] | 1338 | // the first point to the ith point for i=3,...,size(polygon); |
---|
[b0732eb] | 1339 | // if this sum is zero |
---|
| 1340 | // then the polygon is a line segment and we have to find its end points |
---|
| 1341 | d=0; |
---|
| 1342 | for (i=3;i<=size(polygon);i++) |
---|
| 1343 | { |
---|
| 1344 | D=polygon[2]-polygon[1],polygon[i]-polygon[1]; |
---|
| 1345 | d=d+abs(det(D)); |
---|
| 1346 | } |
---|
| 1347 | if (d==0) // then polygon is a line segment |
---|
| 1348 | { |
---|
| 1349 | intmat laenge[size(polygon)][size(polygon)]; |
---|
| 1350 | intvec mp; |
---|
[7e8485] | 1351 | // for this collect first all vectors pointing from one lattice |
---|
[b0732eb] | 1352 | // point to the next, |
---|
| 1353 | // compute their pairwise angles and their lengths |
---|
| 1354 | for (i=1;i<=size(polygon)-1;i++) |
---|
[7e8485] | 1355 | { |
---|
[b0732eb] | 1356 | for (j=i+1;j<=size(polygon);j++) |
---|
| 1357 | { |
---|
| 1358 | mp=polygon[i]-polygon[j]; |
---|
| 1359 | laenge[i,j]=abs(gcd(mp[1],mp[2])); |
---|
| 1360 | } |
---|
| 1361 | } |
---|
| 1362 | mp=maxPosInIntmat(laenge); |
---|
| 1363 | list endpoints=polygon[mp[1]],polygon[mp[2]]; |
---|
| 1364 | intvec abstand; |
---|
| 1365 | for (i=1;i<=size(polygon);i++) |
---|
| 1366 | { |
---|
| 1367 | abstand[i]=0; |
---|
| 1368 | if (i<mp[1]) |
---|
| 1369 | { |
---|
| 1370 | abstand[i]=laenge[i,mp[1]]; |
---|
| 1371 | } |
---|
| 1372 | if (i>mp[1]) |
---|
| 1373 | { |
---|
| 1374 | abstand[i]=laenge[mp[1],i]; |
---|
| 1375 | } |
---|
| 1376 | } |
---|
| 1377 | polygon=sortlistbyintvec(polygon,abstand); |
---|
| 1378 | return(list(polygon,endpoints)); |
---|
[7e8485] | 1379 | } |
---|
[b0732eb] | 1380 | /////////////////////////////////////////////////////////////// |
---|
| 1381 | list orderedvertices; // stores the vertices in an ordered way |
---|
[7e8485] | 1382 | list minimisedorderedvertices; // stores the vertices in an ordered way; |
---|
[b0732eb] | 1383 | // redundant ones removed |
---|
[7e8485] | 1384 | list comparevertices; // stores vertices which should be compared to |
---|
[b0732eb] | 1385 | // the testvertex |
---|
| 1386 | orderedvertices[1]=polygon[1]; // set the starting vertex |
---|
| 1387 | minimisedorderedvertices[1]=polygon[1]; // set the starting vertex |
---|
| 1388 | intvec testvertex=polygon[1]; //vertex to which the others have to be compared |
---|
[7e8485] | 1389 | intvec startvertex=polygon[1]; // keep the starting vertex to test, |
---|
[b0732eb] | 1390 | // when the end is reached |
---|
| 1391 | int endtest; // is set to one, when the end is reached |
---|
[7e8485] | 1392 | int startvertexfound;// is 1, once for some testvertex a candidate |
---|
| 1393 | // for the next vertex has been found |
---|
[b0732eb] | 1394 | polygon=delete(polygon,1); // delete the testvertex |
---|
| 1395 | intvec v,w; |
---|
| 1396 | int l=1; // counts the vertices |
---|
[7e8485] | 1397 | // the basic idea is that a vertex can be |
---|
[b0732eb] | 1398 | // the next one on the boundary if all other vertices |
---|
[7e8485] | 1399 | // lie to the right of the vector v pointing |
---|
[b0732eb] | 1400 | // from the testvertex to this one; this can be tested |
---|
[7e8485] | 1401 | // by checking if the determinant of the 2x2-matrix |
---|
[b0732eb] | 1402 | // with first column v and second column the vector w, |
---|
[7e8485] | 1403 | // pointing from the testvertex to the new vertex, |
---|
[b0732eb] | 1404 | // is non-positive; if this is the case for all |
---|
[7e8485] | 1405 | // new vertices, then the one in consideration is |
---|
[b0732eb] | 1406 | // a possible choice for the next vertex on the boundary |
---|
[7e8485] | 1407 | // and it is stored in naechste; we can then order |
---|
[b0732eb] | 1408 | // the candidates according to their distance from |
---|
| 1409 | // the testvertex; then they occur on the boundary in that order! |
---|
| 1410 | while (endtest==0) |
---|
| 1411 | { |
---|
| 1412 | list naechste; // stores the possible choices for the next vertex |
---|
| 1413 | k=1; |
---|
| 1414 | for (i=1;i<=size(polygon);i++) |
---|
| 1415 | { |
---|
| 1416 | d=0; // stores the value of the determinant of (v,w) |
---|
| 1417 | v=polygon[i]-testvertex; // points from the testvertex to the ith vertex |
---|
| 1418 | comparevertices=delete(polygon,i); // we needn't compare v to itself |
---|
[7e8485] | 1419 | // we should compare v to the startvertex-testvertex; |
---|
[b0732eb] | 1420 | // in the first calling of the loop |
---|
[7e8485] | 1421 | // this is irrelevant since the difference will be zero; |
---|
[b0732eb] | 1422 | // however, later on it will |
---|
[7e8485] | 1423 | // be vital, since we delete the vertices |
---|
[b0732eb] | 1424 | // which we have already tested from the list |
---|
[7e8485] | 1425 | // of all vertices, and when all vertices |
---|
[b0732eb] | 1426 | // on the boundary have been found we would |
---|
[7e8485] | 1427 | // therefore find a vertex in the interior |
---|
[b0732eb] | 1428 | // as candidate; but always testing against |
---|
| 1429 | // the starting vertex, this cannot happen |
---|
[7e8485] | 1430 | comparevertices[size(comparevertices)+1]=startvertex; |
---|
[b0732eb] | 1431 | for (j=1;(j<=size(comparevertices)) and (d<=0);j++) |
---|
| 1432 | { |
---|
| 1433 | w=comparevertices[j]-testvertex; // points form the testvertex |
---|
| 1434 | // to the jth vertex |
---|
| 1435 | D=v,w; |
---|
| 1436 | d=det(D); |
---|
| 1437 | } |
---|
[7e8485] | 1438 | if (d<=0) // if all determinants are non-positive, |
---|
[b0732eb] | 1439 | { // then the ith vertex is a candidate |
---|
| 1440 | naechste[k]=list(polygon[i],i,scalarproduct(v,v));// we store the vertex, |
---|
| 1441 | //its position, and its |
---|
| 1442 | k++; // distance from the testvertex |
---|
| 1443 | } |
---|
| 1444 | } |
---|
| 1445 | if (size(naechste)>0) // then a candidate for the next vertex has been found |
---|
[7e8485] | 1446 | { |
---|
[b0732eb] | 1447 | startvertexfound=1; // at least once a candidate has been found |
---|
[7e8485] | 1448 | naechste=sortlist(naechste,3); // we order the candidates according |
---|
[b0732eb] | 1449 | // to their distance from testvertex; |
---|
[7e8485] | 1450 | for (j=1;j<=size(naechste);j++) // then we store them in this |
---|
[b0732eb] | 1451 | { // order in orderedvertices |
---|
| 1452 | l++; |
---|
| 1453 | orderedvertices[l]=naechste[j][1]; |
---|
| 1454 | } |
---|
[7e8485] | 1455 | testvertex=naechste[size(naechste)][1]; // we store the last one as |
---|
[b0732eb] | 1456 | // next testvertex; |
---|
| 1457 | // store the next corner of NSD |
---|
[7e8485] | 1458 | minimisedorderedvertices[size(minimisedorderedvertices)+1]=testvertex; |
---|
| 1459 | naechste=sortlist(naechste,2); // then we reorder the vertices |
---|
[b0732eb] | 1460 | // according to their position |
---|
| 1461 | for (j=size(naechste);j>=1;j--) // and we delete them from the vertices |
---|
| 1462 | { |
---|
| 1463 | polygon=delete(polygon,naechste[j][2]); |
---|
| 1464 | } |
---|
| 1465 | } |
---|
[7e8485] | 1466 | else // that means either that the vertex was inside the polygon, |
---|
| 1467 | { // or that we have reached the last vertex on the boundary |
---|
[b0732eb] | 1468 | // of the polytope |
---|
[7e8485] | 1469 | if (startvertexfound==0) // the vertex was in the interior; |
---|
[b0732eb] | 1470 | { // we delete it and start all over again |
---|
[7e8485] | 1471 | orderedvertices[1]=polygon[1]; |
---|
| 1472 | minimisedorderedvertices[1]=polygon[1]; |
---|
[b0732eb] | 1473 | testvertex=polygon[1]; |
---|
| 1474 | startvertex=polygon[1]; |
---|
| 1475 | polygon=delete(polygon,1); |
---|
| 1476 | } |
---|
[7e8485] | 1477 | else // we have reached the last vertex on the boundary of |
---|
[b0732eb] | 1478 | { // the polytope and can stop |
---|
| 1479 | endtest=1; |
---|
| 1480 | } |
---|
| 1481 | } |
---|
| 1482 | kill naechste; |
---|
| 1483 | } |
---|
[7e8485] | 1484 | // test if the first vertex in minimisedorderedvertices |
---|
[b0732eb] | 1485 | // is on the same line with the second and |
---|
[7e8485] | 1486 | // the last, i.e. if we started our search in the |
---|
[b0732eb] | 1487 | // middle of a face; if so, delete it |
---|
| 1488 | v=minimisedorderedvertices[2]-minimisedorderedvertices[1]; |
---|
| 1489 | w=minimisedorderedvertices[size(minimisedorderedvertices)]-minimisedorderedvertices[1]; |
---|
| 1490 | D=v,w; |
---|
| 1491 | if (det(D)==0) |
---|
| 1492 | { |
---|
| 1493 | minimisedorderedvertices=delete(minimisedorderedvertices,1); |
---|
| 1494 | } |
---|
[7e8485] | 1495 | // test if the first vertex in minimisedorderedvertices |
---|
[b0732eb] | 1496 | // is on the same line with the two |
---|
[7e8485] | 1497 | // last ones, i.e. if we started our search at the end of a face; |
---|
[b0732eb] | 1498 | // if so, delete it |
---|
| 1499 | v=minimisedorderedvertices[size(minimisedorderedvertices)-1]-minimisedorderedvertices[1]; |
---|
| 1500 | w=minimisedorderedvertices[size(minimisedorderedvertices)]-minimisedorderedvertices[1]; |
---|
| 1501 | D=v,w; |
---|
| 1502 | if (det(D)==0) |
---|
| 1503 | { |
---|
| 1504 | minimisedorderedvertices=delete(minimisedorderedvertices,size(minimisedorderedvertices)); |
---|
| 1505 | } |
---|
| 1506 | return(list(orderedvertices,minimisedorderedvertices)); |
---|
| 1507 | } |
---|
| 1508 | example |
---|
| 1509 | { |
---|
| 1510 | "EXAMPLE:"; |
---|
| 1511 | echo=2; |
---|
| 1512 | // the following lattice points in the plane define a polygon |
---|
| 1513 | list polygon=intvec(0,0),intvec(3,1),intvec(1,0),intvec(2,0), |
---|
| 1514 | intvec(1,1),intvec(3,2),intvec(1,2),intvec(2,3), |
---|
| 1515 | intvec(2,4); |
---|
| 1516 | // we compute its boundary |
---|
| 1517 | list boundarypolygon=findOrientedBoundary(polygon); |
---|
| 1518 | // the points on the boundary ordered clockwise are boundarypolygon[1] |
---|
| 1519 | boundarypolygon[1]; |
---|
| 1520 | // the vertices of the boundary are boundarypolygon[2] |
---|
| 1521 | boundarypolygon[2]; |
---|
| 1522 | } |
---|
| 1523 | |
---|
| 1524 | |
---|
| 1525 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 1526 | |
---|
| 1527 | proc cyclePoints (list triang,list points,int pt) |
---|
| 1528 | "USAGE: cyclePoints(triang,points,pt) triang,points list, pt int |
---|
[7e8485] | 1529 | ASSUME: - points is a list of integer vectors describing the lattice |
---|
[b0732eb] | 1530 | points of a marked polygon; |
---|
[7e8485] | 1531 | @* - triang is a list of integer vectors describing a triangulation |
---|
| 1532 | of the marked polygon in the sense that an integer vector of |
---|
| 1533 | the form (i,j,k) describes the triangle formed by polygon[i], |
---|
[b0732eb] | 1534 | polygon[j] and polygon[k]; |
---|
[7e8485] | 1535 | @* - pt is an integer between 1 and size(points), singling out a |
---|
[b0732eb] | 1536 | lattice point among the marked points |
---|
[7e8485] | 1537 | PURPOSE: consider the convex lattice polygon, say P, spanned by all lattice |
---|
| 1538 | points in points which in the triangulation triang are connected |
---|
| 1539 | to the point points[pt]; the procedure computes all marked points |
---|
[b0732eb] | 1540 | in points which lie on the boundary of that polygon, ordered |
---|
| 1541 | clockwise |
---|
[7e8485] | 1542 | RETURN: list, of integer vectors which are the coordinates of the lattice |
---|
| 1543 | points on the boundary of the above mentioned polygon P, if |
---|
| 1544 | this polygon is not the empty set (that would be the case if |
---|
| 1545 | points[pt] is not a vertex of any triangle in the |
---|
[b0732eb] | 1546 | triangulation); otherwise return the empty list |
---|
| 1547 | EXAMPLE: example cyclePoints; shows an example" |
---|
| 1548 | { |
---|
| 1549 | int i,j; // indices |
---|
[7e8485] | 1550 | list v; // saves the indices of lattice points connected to the |
---|
[b0732eb] | 1551 | // interior point in the triangulation |
---|
| 1552 | // save all points in triangulations containing pt in v |
---|
| 1553 | for (i=1;i<=size(triang);i++) |
---|
| 1554 | { |
---|
| 1555 | if ((triang[i][1]==pt) or (triang[i][2]==pt) or (triang[i][3]==pt)) |
---|
| 1556 | { |
---|
| 1557 | j++; |
---|
| 1558 | v[3*j-2]=triang[i][1]; |
---|
| 1559 | v[3*j-1]=triang[i][2]; |
---|
| 1560 | v[3*j]=triang[i][3]; |
---|
| 1561 | } |
---|
| 1562 | } |
---|
| 1563 | if (size(v)==0) |
---|
| 1564 | { |
---|
| 1565 | return(list()); |
---|
| 1566 | } |
---|
| 1567 | // remove pt itself and redundancies in v |
---|
| 1568 | for (i=size(v);i>=1;i--) |
---|
| 1569 | { |
---|
| 1570 | j=1; |
---|
| 1571 | while ((j<i) and (v[i]!=v[j])) |
---|
| 1572 | { |
---|
| 1573 | j++; |
---|
| 1574 | } |
---|
| 1575 | if ((j<i) or (v[i]==pt)) |
---|
| 1576 | { |
---|
| 1577 | v=delete(v,i); |
---|
| 1578 | } |
---|
| 1579 | } |
---|
| 1580 | // save in pts the coordinates of the points with indices in v |
---|
| 1581 | list pts; |
---|
| 1582 | for (i=1;i<=size(v);i++) |
---|
| 1583 | { |
---|
| 1584 | pts[i]=points[v[i]]; |
---|
| 1585 | } |
---|
[7e8485] | 1586 | // consider the convex polytope spanned by the points in pts, |
---|
[b0732eb] | 1587 | // find the points on the |
---|
| 1588 | // boundary and order them clockwise |
---|
| 1589 | return(findOrientedBoundary(pts)[1]); |
---|
| 1590 | } |
---|
| 1591 | example |
---|
| 1592 | { |
---|
| 1593 | "EXAMPLE:"; |
---|
| 1594 | echo=2; |
---|
[7e8485] | 1595 | // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) |
---|
[b0732eb] | 1596 | // with all integer points as markings |
---|
| 1597 | list points=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0), |
---|
| 1598 | intvec(0,0),intvec(2,1),intvec(0,1),intvec(1,2), |
---|
| 1599 | intvec(0,2),intvec(0,3); |
---|
[7e8485] | 1600 | // define a triangulation |
---|
[b0732eb] | 1601 | list triang=intvec(1,2,5),intvec(1,5,7),intvec(1,7,9),intvec(8,9,10), |
---|
| 1602 | intvec(1,8,9),intvec(1,2,8); |
---|
| 1603 | // compute the points connected to (1,1) in triang |
---|
| 1604 | cyclePoints(triang,points,1); |
---|
| 1605 | } |
---|
| 1606 | |
---|
| 1607 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 1608 | |
---|
| 1609 | proc latticeArea (list polygon) |
---|
| 1610 | "USAGE: latticeArea(polygon); polygon list |
---|
| 1611 | ASSUME: polygon is a list of integer vectors in the plane |
---|
[7e8485] | 1612 | RETURN: int, the lattice area of the convex hull of the lattice points in |
---|
[b0732eb] | 1613 | polygon, i.e. twice the Euclidean area |
---|
| 1614 | EXAMPLE: example polygonlatticeArea; shows an example" |
---|
| 1615 | { |
---|
| 1616 | list pg=findOrientedBoundary(polygon)[2]; |
---|
| 1617 | int area; |
---|
| 1618 | intmat M[2][2]; |
---|
| 1619 | for (int i=2;i<=size(pg)-1;i++) |
---|
| 1620 | { |
---|
| 1621 | M[1,1..2]=pg[i]-pg[1]; |
---|
| 1622 | M[2,1..2]=pg[i+1]-pg[1]; |
---|
| 1623 | area=area+abs(det(M)); |
---|
| 1624 | } |
---|
| 1625 | return(area); |
---|
| 1626 | } |
---|
| 1627 | example |
---|
| 1628 | { |
---|
| 1629 | "EXAMPLE:"; |
---|
| 1630 | echo=2; |
---|
| 1631 | // define a polygon with lattice area 5 |
---|
| 1632 | list polygon=intvec(1,2),intvec(1,0),intvec(2,0),intvec(1,1), |
---|
| 1633 | intvec(2,1),intvec(0,0); |
---|
| 1634 | latticeArea(polygon); |
---|
| 1635 | } |
---|
| 1636 | |
---|
| 1637 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 1638 | |
---|
| 1639 | proc picksFormula (list polygon) |
---|
| 1640 | "USAGE: picksFormula(polygon); polygon list |
---|
[7e8485] | 1641 | ASSUME: polygon is a list of integer vectors in the plane and consider their |
---|
| 1642 | convex hull C |
---|
| 1643 | RETURN: list, L of three integersthe |
---|
[b0732eb] | 1644 | @* L[1] : the lattice area of C, i.e. twice the Euclidean area |
---|
| 1645 | @* L[2] : the number of lattice points on the boundary of C |
---|
| 1646 | @* L[3] : the number of interior lattice points of C |
---|
| 1647 | NOTE: the integers in L are related by Pick's formula, namely: L[1]=L[2]+2*L[3]-2 |
---|
| 1648 | EXAMPLE: example picksFormula; shows an example" |
---|
| 1649 | { |
---|
| 1650 | list pg=findOrientedBoundary(polygon)[2]; |
---|
| 1651 | int area,bdpts,i; |
---|
| 1652 | intmat M[2][2]; |
---|
| 1653 | // compute the lattice area of the polygon, i.e. twice the Euclidean area |
---|
| 1654 | for (i=2;i<=size(pg)-1;i++) |
---|
| 1655 | { |
---|
| 1656 | M[1,1..2]=pg[i]-pg[1]; |
---|
| 1657 | M[2,1..2]=pg[i+1]-pg[1]; |
---|
| 1658 | area=area+abs(det(M)); |
---|
| 1659 | } |
---|
| 1660 | // compute the number of lattice points on the boundary |
---|
| 1661 | intvec edge; |
---|
| 1662 | pg[size(pg)+1]=pg[1]; |
---|
| 1663 | for (i=1;i<=size(pg)-1;i++) |
---|
| 1664 | { |
---|
| 1665 | edge=pg[i]-pg[i+1]; |
---|
| 1666 | bdpts=bdpts+abs(gcd(edge[1],edge[2])); |
---|
| 1667 | } |
---|
[7e8485] | 1668 | // Pick's formula says that the lattice area A, the number g of interior |
---|
[b0732eb] | 1669 | // points and |
---|
| 1670 | // the number b of boundary points are connected by the formula: A=b+2g-2 |
---|
| 1671 | return(list(area,bdpts,(area-bdpts+2)/2)); |
---|
| 1672 | } |
---|
| 1673 | example |
---|
| 1674 | { |
---|
| 1675 | "EXAMPLE:"; |
---|
| 1676 | echo=2; |
---|
| 1677 | // define a polygon with lattice area 5 |
---|
| 1678 | list polygon=intvec(1,2),intvec(1,0),intvec(2,0),intvec(1,1), |
---|
| 1679 | intvec(2,1),intvec(0,0); |
---|
| 1680 | list pick=picksFormula(polygon); |
---|
| 1681 | // the lattice area of the polygon is: |
---|
| 1682 | pick[1]; |
---|
| 1683 | // the number of lattice points on the boundary is: |
---|
| 1684 | pick[2]; |
---|
| 1685 | // the number of interior lattice points is: |
---|
| 1686 | pick[3]; |
---|
| 1687 | // the number's are related by Pick's formula: |
---|
| 1688 | pick[1]-pick[2]-2*pick[3]+2; |
---|
| 1689 | } |
---|
| 1690 | |
---|
| 1691 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 1692 | |
---|
| 1693 | proc ellipticNF (list polygon) |
---|
| 1694 | "USAGE: ellipticNF(polygon); polygon list |
---|
[7e8485] | 1695 | ASSUME: polygon is a list of integer vectors in the plane such that their |
---|
| 1696 | convex hull C has precisely one interior lattice point; i.e. C is the |
---|
[b0732eb] | 1697 | Newton polygon of an elliptic curve |
---|
[7e8485] | 1698 | PURPOSE: compute the normal form of the polygon with respect to the unimodular |
---|
[b0732eb] | 1699 | affine transformations T=A*x+v; there are sixteen different normal forms |
---|
[7e8485] | 1700 | (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons |
---|
| 1701 | and the number 12. Amer. Math. Monthly 107 (2000), no. 3, |
---|
[b0732eb] | 1702 | 238--250.) |
---|
| 1703 | RETURN: list, L such that |
---|
[7e8485] | 1704 | @* L[1] : list whose entries are the vertices of the normal form of |
---|
[b0732eb] | 1705 | the polygon |
---|
| 1706 | @* L[2] : the matrix A of the unimodular transformation |
---|
| 1707 | @* L[3] : the translation vector v of the unimodular transformation |
---|
[7e8485] | 1708 | @* L[4] : list such that the ith entry is the image of polygon[i] |
---|
[b0732eb] | 1709 | under the unimodular transformation T |
---|
| 1710 | EXAMPLE: example ellipticNF; shows an example" |
---|
| 1711 | { |
---|
| 1712 | int i; // index |
---|
| 1713 | intvec edge; // stores the vector of an edge |
---|
[7e8485] | 1714 | intvec boundary; // stores lattice lengths of the edges of the Newton cycle |
---|
[b0732eb] | 1715 | // find the vertices of the Newton cycle and order it clockwise |
---|
| 1716 | list pg=findOrientedBoundary(polygon)[2]; |
---|
| 1717 | // check if there is precisely one interior point in the Newton polygon |
---|
| 1718 | if (picksFormula(pg)[3]!=1) |
---|
| 1719 | { |
---|
| 1720 | ERROR("The polygon has not precisely one interior point!"); |
---|
| 1721 | } |
---|
| 1722 | // insert the first vertex at the end once again |
---|
| 1723 | pg[size(pg)+1]=pg[1]; |
---|
| 1724 | // compute the number of lattice points on each edge |
---|
| 1725 | for (i=1;i<=size(pg)-1;i++) |
---|
| 1726 | { |
---|
| 1727 | edge=pg[i]-pg[i+1]; |
---|
| 1728 | boundary[i]=1+abs(gcd(edge[1],edge[2])); |
---|
| 1729 | } |
---|
| 1730 | // store the values of boundary once more adding the first two at the end |
---|
| 1731 | intvec tboundary=boundary,boundary[1],boundary[2]; |
---|
| 1732 | // sort boundary in an asecending way |
---|
| 1733 | intvec sbd=sortintvec(boundary); |
---|
| 1734 | // find the first edge having the maximal number of lattice points |
---|
| 1735 | int max=maxPosInIntvec(boundary); |
---|
| 1736 | // some computations have to be done over the rationals |
---|
| 1737 | ring transformationring=0,x,lp; |
---|
| 1738 | intvec trans; // stores the vector by which we have to translate the polygon |
---|
| 1739 | intmat A[2][2]; // stores the matrix by which we have to transform the polygon |
---|
[7e8485] | 1740 | matrix M[3][3]; // stores the projective coordinates of the points |
---|
[b0732eb] | 1741 | // which are to be transformed |
---|
[7e8485] | 1742 | matrix N[3][3]; // stores the projective coordinates of the points to |
---|
[b0732eb] | 1743 | // which M is to be transformed |
---|
[7e8485] | 1744 | intmat T[3][3]; // stores the unimodular affine transformation in |
---|
[b0732eb] | 1745 | // projective form |
---|
| 1746 | // add the second point of pg once again at the end |
---|
| 1747 | pg=insert(pg,pg[2],size(pg)); |
---|
[7e8485] | 1748 | // if there is only one edge which has the maximal number of lattice points, |
---|
[b0732eb] | 1749 | // then M should be: |
---|
| 1750 | M=pg[max],1,pg[max+1],1,pg[max+2],1; |
---|
| 1751 | // consider the 16 different cases which can occur: |
---|
| 1752 | // Case 1: |
---|
| 1753 | if (sbd==intvec(2,2,2)) |
---|
| 1754 | { |
---|
| 1755 | N=0,1,1,1,2,1,2,0,1; |
---|
| 1756 | } |
---|
| 1757 | // Case 2: |
---|
| 1758 | if (sbd==intvec(2,2,3)) |
---|
| 1759 | { |
---|
| 1760 | N=2,0,1,0,0,1,1,2,1; |
---|
| 1761 | } |
---|
| 1762 | // Case 3: |
---|
| 1763 | if (sbd==intvec(2,3,4)) |
---|
| 1764 | { |
---|
| 1765 | // here the orientation of the Newton polygon is important ! |
---|
| 1766 | if (tboundary[max+1]==3) |
---|
| 1767 | { |
---|
| 1768 | N=3,0,1,0,0,1,0,2,1; |
---|
| 1769 | } |
---|
| 1770 | else |
---|
| 1771 | { |
---|
| 1772 | N=0,0,1,3,0,1,0,2,1; |
---|
| 1773 | } |
---|
| 1774 | } |
---|
| 1775 | // Case 4: |
---|
| 1776 | if (sbd==intvec(3,3,5)) |
---|
| 1777 | { |
---|
| 1778 | N=4,0,1,0,0,1,0,2,1; |
---|
| 1779 | } |
---|
| 1780 | // Case 5: |
---|
| 1781 | if (sbd==intvec(4,4,4)) |
---|
| 1782 | { |
---|
| 1783 | N=3,0,1,0,0,1,0,3,1; |
---|
| 1784 | } |
---|
| 1785 | // Case 6+7: |
---|
| 1786 | if (sbd==intvec(2,2,2,2)) |
---|
| 1787 | { |
---|
| 1788 | // there are two different polygons which has four edges all of length 2, |
---|
| 1789 | // but only one of them has two edges whose direction vectors form a matrix |
---|
| 1790 | // of determinant 3 |
---|
| 1791 | A=pg[1]-pg[2],pg[3]-pg[2]; |
---|
| 1792 | while ((max<4) and (det(A)!=3)) |
---|
| 1793 | { |
---|
| 1794 | max++; |
---|
| 1795 | A=pg[max]-pg[max+1],pg[max+2]-pg[max+1]; |
---|
| 1796 | } |
---|
| 1797 | // Case 6: |
---|
| 1798 | if (det(A)==3) |
---|
| 1799 | { |
---|
| 1800 | M=pg[max],1,pg[max+1],1,pg[max+2],1; |
---|
| 1801 | N=1,0,1,0,2,1,2,1,1; |
---|
| 1802 | } |
---|
| 1803 | // Case 7: |
---|
| 1804 | else |
---|
| 1805 | { |
---|
| 1806 | N=2,1,1,1,0,1,0,1,1; |
---|
| 1807 | } |
---|
| 1808 | } |
---|
| 1809 | // Case 8: |
---|
| 1810 | if (sbd==intvec(2,2,2,3)) |
---|
| 1811 | { |
---|
| 1812 | // the orientation of the polygon is important |
---|
| 1813 | A=pg[max]-pg[max+1],pg[max+2]-pg[max+1]; |
---|
| 1814 | if (det(A)==2) |
---|
| 1815 | { |
---|
| 1816 | N=2,0,1,0,0,1,0,1,1; |
---|
| 1817 | } |
---|
| 1818 | else |
---|
| 1819 | { |
---|
| 1820 | N=0,0,1,2,0,1,1,2,1; |
---|
| 1821 | } |
---|
| 1822 | } |
---|
| 1823 | // Case 9: |
---|
| 1824 | if (sbd==intvec(2,2,3,3)) |
---|
| 1825 | { |
---|
| 1826 | // if max==1, then the 5th entry in tboundary is the same as the first |
---|
| 1827 | if (max==1) |
---|
| 1828 | { |
---|
| 1829 | max=5; |
---|
| 1830 | } |
---|
| 1831 | // if boundary=3,2,2,3 then set max=4 |
---|
| 1832 | if (tboundary[max+1]!=3) |
---|
| 1833 | { |
---|
| 1834 | max=4; |
---|
| 1835 | } |
---|
| 1836 | M=pg[max],1,pg[max+1],1,pg[max+2],1; |
---|
| 1837 | // the orientation of the polygon matters |
---|
[7e8485] | 1838 | A=pg[max-1]-pg[max],pg[max+1]-pg[max]; |
---|
[b0732eb] | 1839 | if (det(A)==4) |
---|
| 1840 | { |
---|
| 1841 | N=2,0,1,0,0,1,0,2,1; |
---|
| 1842 | } |
---|
| 1843 | else |
---|
| 1844 | { |
---|
| 1845 | N=0,2,1,0,0,1,2,0,1; |
---|
| 1846 | } |
---|
| 1847 | } |
---|
| 1848 | // Case 10: |
---|
| 1849 | if (sbd==intvec(2,2,3,4)) |
---|
| 1850 | { |
---|
| 1851 | // the orientation of the polygon matters |
---|
| 1852 | if (tboundary[max+1]==3) |
---|
| 1853 | { |
---|
| 1854 | N=3,0,1,0,0,1,0,2,1; |
---|
| 1855 | } |
---|
| 1856 | else |
---|
| 1857 | { |
---|
| 1858 | N=0,0,1,3,0,1,2,1,1; |
---|
| 1859 | } |
---|
| 1860 | } |
---|
| 1861 | // Case 11: |
---|
| 1862 | if (sbd==intvec(2,3,3,4)) |
---|
| 1863 | { |
---|
| 1864 | N=3,0,1,0,0,1,0,2,1; |
---|
| 1865 | } |
---|
| 1866 | // Case 12: |
---|
| 1867 | if (sbd==intvec(3,3,3,3)) |
---|
| 1868 | { |
---|
| 1869 | N=2,0,1,0,0,1,0,2,1; |
---|
| 1870 | } |
---|
| 1871 | // Case 13: |
---|
| 1872 | if (sbd==intvec(2,2,2,2,2)) |
---|
| 1873 | { |
---|
| 1874 | // compute the angles of the polygon vertices |
---|
| 1875 | intvec dt; |
---|
| 1876 | for (i=1;i<=5;i++) |
---|
| 1877 | { |
---|
| 1878 | A=pg[i]-pg[i+1],pg[i+2]-pg[i+1]; |
---|
| 1879 | dt[i]=det(A); |
---|
| 1880 | } |
---|
| 1881 | dt[6]=dt[1]; |
---|
| 1882 | // find the vertex to be mapped to (0,1) |
---|
| 1883 | max=1; |
---|
| 1884 | while ((dt[max]!=2) or (dt[max+1]!=2)) |
---|
| 1885 | { |
---|
| 1886 | max++; |
---|
[7e8485] | 1887 | } |
---|
[b0732eb] | 1888 | M=pg[max],1,pg[max+1],1,pg[max+2],1; |
---|
| 1889 | N=0,1,1,1,2,1,2,1,1; |
---|
| 1890 | } |
---|
| 1891 | // Case 14: |
---|
| 1892 | if (sbd==intvec(2,2,2,2,3)) |
---|
| 1893 | { |
---|
| 1894 | N=2,0,1,0,0,1,0,1,1; |
---|
| 1895 | } |
---|
| 1896 | // Case 15: |
---|
| 1897 | if (sbd==intvec(2,2,2,3,3)) |
---|
| 1898 | { |
---|
| 1899 | // find the vertix to be mapped to (2,0) |
---|
| 1900 | if (tboundary[max+1]!=3) |
---|
| 1901 | { |
---|
| 1902 | max=5; |
---|
| 1903 | M=pg[max],1,pg[max+1],1,pg[max+2],1; |
---|
| 1904 | } |
---|
| 1905 | N=2,0,1,0,0,1,0,2,1; |
---|
| 1906 | } |
---|
| 1907 | // Case 16: |
---|
| 1908 | if (sbd==intvec(2,2,2,2,2,2)) |
---|
| 1909 | { |
---|
| 1910 | N=2,0,1,1,0,1,0,1,1; |
---|
| 1911 | } |
---|
| 1912 | // we have to transpose the matrices M and N |
---|
| 1913 | M=transpose(M); |
---|
| 1914 | N=transpose(N); |
---|
| 1915 | // compute the unimodular affine transformation, which is of the form |
---|
| 1916 | // A11 A12 | T1 |
---|
| 1917 | // A21 A22 | T2 |
---|
| 1918 | // 0 0 | 1 |
---|
| 1919 | T=matrixtointmat(N*inverse(M)); |
---|
| 1920 | // the upper-left 2x2-block is A |
---|
| 1921 | A=T[1..2,1..2]; |
---|
| 1922 | // the upper-right 2x1-block is the translation vector |
---|
| 1923 | trans=T[1,3],T[2,3]; |
---|
| 1924 | // transform now the lattice points of the polygon with respect to A and T |
---|
| 1925 | list nf; |
---|
| 1926 | for (i=1;i<=size(polygon);i++) |
---|
| 1927 | { |
---|
| 1928 | intmat V[2][1]=polygon[i]; |
---|
| 1929 | V=A*V; |
---|
| 1930 | nf[i]=intvec(V[1,1]+trans[1],V[2,1]+trans[2]); |
---|
| 1931 | kill V; |
---|
| 1932 | } |
---|
| 1933 | return(list(findOrientedBoundary(nf)[2],A,trans,nf)); |
---|
| 1934 | } |
---|
| 1935 | example |
---|
| 1936 | { |
---|
| 1937 | "EXAMPLE:"; |
---|
| 1938 | echo=2; |
---|
| 1939 | ring r=0,(x,y),dp; |
---|
| 1940 | // the Newton polygon of the following polynomial |
---|
| 1941 | // has precisely one interior point |
---|
| 1942 | poly f=x22y11+x19y10+x17y9+x16y9+x12y7+x9y6+x7y5+x2y3; |
---|
| 1943 | list polygon=newtonPolytopeLP(f); |
---|
| 1944 | // its lattice points are |
---|
| 1945 | polygon; |
---|
| 1946 | // find its normal form |
---|
| 1947 | list nf=ellipticNF(polygon); |
---|
| 1948 | // the vertices of the normal form are |
---|
| 1949 | nf[1]; |
---|
[7e8485] | 1950 | // it has been transformed by the unimodular affine transformation A*x+v |
---|
[b0732eb] | 1951 | // with matrix A |
---|
| 1952 | nf[2]; |
---|
| 1953 | // and translation vector v |
---|
| 1954 | nf[3]; |
---|
| 1955 | // the 3rd lattice point ... |
---|
| 1956 | polygon[3]; |
---|
| 1957 | // ... has been transformed to |
---|
| 1958 | nf[4][3]; |
---|
| 1959 | } |
---|
| 1960 | |
---|
| 1961 | |
---|
| 1962 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 1963 | |
---|
| 1964 | proc ellipticNFDB (int n,list #) |
---|
| 1965 | "USAGE: ellipticNFDB(n[,#]); n int, # list |
---|
| 1966 | ASSUME: n is an integer between 1 and 16 |
---|
[7e8485] | 1967 | PURPOSE: this is a database storing the 16 normal forms of planar polygons with |
---|
[b0732eb] | 1968 | precisely one interior point up to unimodular affine transformations |
---|
[7e8485] | 1969 | @* (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons |
---|
[b0732eb] | 1970 | and the number 12. Amer. Math. Monthly 107 (2000), no. 3, |
---|
| 1971 | 238--250.) |
---|
| 1972 | RETURN: list, L such that |
---|
[7e8485] | 1973 | @* L[1] : list whose entries are the vertices of the nth normal form |
---|
| 1974 | @* L[2] : list whose entries are all the lattice points of the |
---|
| 1975 | nth normal form |
---|
| 1976 | @* L[3] : only present if the optional parameter # is present, and |
---|
| 1977 | then it is a polynomial in the variables (x,y) whose |
---|
[b0732eb] | 1978 | Newton polygon is the nth normal form |
---|
[7e8485] | 1979 | NOTE: the optional parameter is only allowed if the basering has the |
---|
[b0732eb] | 1980 | variables x and y |
---|
| 1981 | EXAMPLE: example ellipticNFDB; shows an example" |
---|
| 1982 | { |
---|
| 1983 | if ((n<1) or (n>16)) |
---|
| 1984 | { |
---|
| 1985 | ERROR("n is not between 1 and 16."); |
---|
| 1986 | } |
---|
| 1987 | if (size(#)>0) |
---|
| 1988 | { |
---|
| 1989 | if ((defined(x)==0) or (defined(y)==0)) |
---|
| 1990 | { |
---|
| 1991 | ERROR("The variables x and y are not defined."); |
---|
| 1992 | } |
---|
| 1993 | } |
---|
| 1994 | if ((defined(x)==0) or (defined(y)==0)) |
---|
| 1995 | { |
---|
| 1996 | ring nfring=0,(x,y),dp; |
---|
| 1997 | } |
---|
| 1998 | // store the normal forms as polynomials |
---|
| 1999 | list nf=x2+y+xy2,x2+x+1+xy2,x3+x2+x+1+y2+y,x4+x3+x2+x+1+y2+y+x2y,x3+x2+x+1+x2y+y+xy2+y2+y3, |
---|
| 2000 | x2+x+x2y+y2,x2y+x+y+xy2,x2+x+1+y+xy2,x2+x+1+y+xy2+y2,x3+x2+x+1+x2y+y+y2,x3+x2+x+1+x2y+y+xy2+y2, |
---|
| 2001 | x2+x+1+x2y+y+x2y2+xy2+y2,x+1+x2y+y+xy2,x2+x+1+x2y+y+xy2,x2+x+1+x2y+y+xy2+y2,x2+x+x2y+y+xy2+y2; |
---|
| 2002 | list pg=newtonPolytopeLP(nf[n]); |
---|
| 2003 | if (size(#)==0) |
---|
| 2004 | { |
---|
| 2005 | return(list(findOrientedBoundary(pg)[2],pg)); |
---|
| 2006 | } |
---|
| 2007 | else |
---|
| 2008 | { |
---|
| 2009 | return(list(findOrientedBoundary(pg)[2],pg,nf[n])); |
---|
| 2010 | } |
---|
| 2011 | } |
---|
| 2012 | example |
---|
| 2013 | { |
---|
| 2014 | "EXAMPLE:"; |
---|
| 2015 | echo=2; |
---|
| 2016 | list nf=ellipticNFDB(5); |
---|
| 2017 | // the vertices of the 5th normal form are |
---|
| 2018 | nf[1]; |
---|
| 2019 | // its lattice points are |
---|
| 2020 | nf[2]; |
---|
| 2021 | } |
---|
| 2022 | |
---|
| 2023 | |
---|
| 2024 | ///////////////////////////////////////////////////////////////////////////////// |
---|
| 2025 | ///////////////////////////////////////////////////////////////////////////////// |
---|
| 2026 | /// AUXILARY PROCEDURES, WHICH ARE DECLARED STATIC |
---|
| 2027 | ///////////////////////////////////////////////////////////////////////////////// |
---|
| 2028 | ///////////////////////////////////////////////////////////////////////////////// |
---|
| 2029 | /// - scalarproduct |
---|
| 2030 | /// - intmatcoldelete |
---|
| 2031 | /// - intmatconcat |
---|
| 2032 | /// - sortlist |
---|
| 2033 | /// - minInList |
---|
| 2034 | /// - stringdelete |
---|
| 2035 | /// - abs |
---|
| 2036 | /// - commondenominator |
---|
| 2037 | /// - maxPosInIntvec |
---|
| 2038 | /// - maxPosInIntmat |
---|
| 2039 | /// - sortintvec |
---|
| 2040 | /// - matrixtointmat |
---|
| 2041 | ///////////////////////////////////////////////////////////////////////////////// |
---|
| 2042 | |
---|
| 2043 | static proc scalarproduct (intvec w,intvec v) |
---|
| 2044 | "USAGE: scalarproduct(w,v); w,v intvec |
---|
[7e8485] | 2045 | ASSUME: w and v are integer vectors of the same length |
---|
[b0732eb] | 2046 | RETURN: int, the scalarproduct of v and w |
---|
| 2047 | NOTE: the procedure is called by findOrientedBoundary" |
---|
| 2048 | { |
---|
| 2049 | int sp; |
---|
| 2050 | for (int i=1;i<=size(w);i++) |
---|
| 2051 | { |
---|
| 2052 | sp=sp+v[i]*w[i]; |
---|
| 2053 | } |
---|
| 2054 | return(sp); |
---|
| 2055 | } |
---|
| 2056 | |
---|
| 2057 | static proc intmatcoldelete (intmat w,int i) |
---|
| 2058 | "USAGE: intmatcoldelete(w,i); w intmat, i int |
---|
| 2059 | RETURN: intmat, the integer matrix w with the ith comlumn deleted |
---|
| 2060 | NOTE: the procedure is called by intmatsort and normalFan" |
---|
| 2061 | { |
---|
| 2062 | if ((i<1) or (i>ncols(w)) or (ncols(w)==1)) |
---|
| 2063 | { |
---|
| 2064 | return(w); |
---|
| 2065 | } |
---|
| 2066 | if (i==1) |
---|
| 2067 | { |
---|
| 2068 | intmat M[nrows(w)][ncols(w)-1]=w[1..nrows(w),2..ncols(w)]; |
---|
| 2069 | return(M); |
---|
| 2070 | } |
---|
| 2071 | if (i==ncols(w)) |
---|
| 2072 | { |
---|
| 2073 | intmat M[nrows(w)][ncols(w)-1]=w[1..nrows(w),1..ncols(w)-1]; |
---|
| 2074 | return(M); |
---|
| 2075 | } |
---|
| 2076 | else |
---|
| 2077 | { |
---|
| 2078 | intmat M[nrows(w)][i-1]=w[1..nrows(w),1..i-1]; |
---|
| 2079 | intmat N[nrows(w)][ncols(w)-i]=w[1..nrows(w),i+1..ncols(w)]; |
---|
| 2080 | return(intmatconcat(M,N)); |
---|
| 2081 | } |
---|
| 2082 | } |
---|
| 2083 | |
---|
| 2084 | static proc intmatconcat (intmat M,intmat N) |
---|
| 2085 | "USAGE: intmatconcat(M,N); M,N intmat |
---|
| 2086 | RETURN: intmat, M and N concatenated |
---|
| 2087 | NOTE: the procedure is called by intmatcoldelete and sortintmat" |
---|
| 2088 | { |
---|
| 2089 | if (nrows(M)>=nrows(N)) |
---|
| 2090 | { |
---|
| 2091 | int m=nrows(M); |
---|
[7e8485] | 2092 | |
---|
[b0732eb] | 2093 | } |
---|
| 2094 | else |
---|
| 2095 | { |
---|
| 2096 | int m=nrows(N); |
---|
| 2097 | } |
---|
| 2098 | intmat P[m][ncols(M)+ncols(N)]; |
---|
| 2099 | P[1..nrows(M),1..ncols(M)]=M[1..nrows(M),1..ncols(M)]; |
---|
| 2100 | P[1..nrows(N),ncols(M)+1..ncols(M)+ncols(N)]=N[1..nrows(N),1..ncols(N)]; |
---|
| 2101 | return(P); |
---|
| 2102 | } |
---|
| 2103 | |
---|
| 2104 | static proc sortlist (list v,int pos) |
---|
| 2105 | "USAGE: sortlist(v,pos); v list, pos int |
---|
| 2106 | RETURN: list, the list L ordered in an ascending way according to the pos-th entries |
---|
| 2107 | NOTE: called by tropicalCurve" |
---|
| 2108 | { |
---|
| 2109 | if(size(v)==1) |
---|
| 2110 | { |
---|
| 2111 | return(v); |
---|
| 2112 | } |
---|
| 2113 | list w=minInList(v,pos); |
---|
| 2114 | v=delete(v,w[2]); |
---|
| 2115 | v=sortlist(v,pos); |
---|
| 2116 | v=list(w[1])+v; |
---|
| 2117 | return(v); |
---|
| 2118 | } |
---|
| 2119 | |
---|
| 2120 | static proc minInList (list v,int pos) |
---|
| 2121 | "USAGE: minInList(v,pos); v list, pos int |
---|
| 2122 | RETURN: list, (v[i],i) such that v[i][pos] is minimal |
---|
| 2123 | NOTE: called by sortlist" |
---|
| 2124 | { |
---|
| 2125 | int min=v[1][pos]; |
---|
| 2126 | int minpos=1; |
---|
| 2127 | for (int i=2;i<=size(v);i++) |
---|
| 2128 | { |
---|
| 2129 | if (v[i][pos]<min) |
---|
| 2130 | { |
---|
| 2131 | min=v[i][pos]; |
---|
| 2132 | minpos=i; |
---|
| 2133 | } |
---|
| 2134 | } |
---|
| 2135 | return(list(v[minpos],minpos)); |
---|
| 2136 | } |
---|
| 2137 | |
---|
| 2138 | static proc stringdelete (string w,int i) |
---|
| 2139 | "USAGE: stringdelete(w,i); w string, i int |
---|
| 2140 | RETURN: string, the string w with the ith component deleted |
---|
| 2141 | NOTE: the procedure is called by texnumber and choosegfanvector" |
---|
| 2142 | { |
---|
| 2143 | if ((i>size(w)) or (i<=0)) |
---|
| 2144 | { |
---|
| 2145 | return(w); |
---|
| 2146 | } |
---|
| 2147 | if ((size(w)==1) and (i==1)) |
---|
| 2148 | { |
---|
| 2149 | return(""); |
---|
[7e8485] | 2150 | |
---|
[b0732eb] | 2151 | } |
---|
| 2152 | if (i==1) |
---|
| 2153 | { |
---|
| 2154 | return(w[2..size(w)]); |
---|
| 2155 | } |
---|
| 2156 | if (i==size(w)) |
---|
| 2157 | { |
---|
| 2158 | return(w[1..size(w)-1]); |
---|
| 2159 | } |
---|
| 2160 | else |
---|
| 2161 | { |
---|
| 2162 | string erg=w[1..i-1],w[i+1..size(w)]; |
---|
| 2163 | return(erg); |
---|
| 2164 | } |
---|
| 2165 | } |
---|
| 2166 | |
---|
| 2167 | static proc abs (def n) |
---|
| 2168 | "USAGE: abs(n); n poly or int |
---|
| 2169 | RETURN: poly or int, the absolute value of n" |
---|
| 2170 | { |
---|
| 2171 | if (n>=0) |
---|
| 2172 | { |
---|
| 2173 | return(n); |
---|
| 2174 | } |
---|
| 2175 | else |
---|
| 2176 | { |
---|
| 2177 | return(-n); |
---|
| 2178 | } |
---|
| 2179 | } |
---|
| 2180 | |
---|
| 2181 | static proc commondenominator (matrix M) |
---|
| 2182 | "USAGE: commondenominator(M); M matrix |
---|
| 2183 | ASSUME: the base ring has characteristic zero |
---|
| 2184 | RETURN: int, the lowest common multiple of the denominators of the leading coefficients |
---|
| 2185 | of the entries in M |
---|
| 2186 | NOTE: the procedure is called from polymakeToIntmat" |
---|
| 2187 | { |
---|
| 2188 | int i,j; |
---|
| 2189 | int kgV=1; |
---|
| 2190 | // successively build the lowest common multiple of the denominators of the leading coefficients |
---|
| 2191 | // of the entries in M |
---|
| 2192 | for (i=1;i<=nrows(M);i++) |
---|
| 2193 | { |
---|
| 2194 | for (j=1;j<=ncols(M);j++) |
---|
| 2195 | { |
---|
| 2196 | kgV=lcm(kgV,int(denominator(leadcoef(M[i,j])))); |
---|
| 2197 | } |
---|
| 2198 | } |
---|
| 2199 | return(kgV); |
---|
| 2200 | } |
---|
| 2201 | |
---|
| 2202 | static proc maxPosInIntvec (intvec v) |
---|
| 2203 | "USAGE: maxPosInIntvec(v); v intvec |
---|
| 2204 | RETURN: int, the first position of a maximal entry in v |
---|
| 2205 | NOTE: called by sortintmat" |
---|
| 2206 | { |
---|
| 2207 | int max=v[1]; |
---|
| 2208 | int maxpos=1; |
---|
| 2209 | for (int i=2;i<=size(v);i++) |
---|
| 2210 | { |
---|
| 2211 | if (v[i]>max) |
---|
| 2212 | { |
---|
| 2213 | max=v[i]; |
---|
| 2214 | maxpos=i; |
---|
| 2215 | } |
---|
| 2216 | } |
---|
| 2217 | return(maxpos); |
---|
| 2218 | } |
---|
| 2219 | |
---|
| 2220 | static proc maxPosInIntmat (intmat v) |
---|
| 2221 | "USAGE: maxPosInIntmat(v); v intmat |
---|
| 2222 | ASSUME: v has a unique maximal entry |
---|
| 2223 | RETURN: intvec, the position (i,j) of the maximal entry in v |
---|
| 2224 | NOTE: called by findOrientedBoundary" |
---|
| 2225 | { |
---|
| 2226 | int max=v[1,1]; |
---|
| 2227 | intvec maxpos=1,1; |
---|
| 2228 | int i,j; |
---|
| 2229 | for (i=1;i<=nrows(v);i++) |
---|
| 2230 | { |
---|
| 2231 | for (j=1;j<=ncols(v);j++) |
---|
| 2232 | { |
---|
| 2233 | if (v[i,j]>max) |
---|
| 2234 | { |
---|
| 2235 | max=v[i,j]; |
---|
| 2236 | maxpos=i,j; |
---|
| 2237 | } |
---|
| 2238 | } |
---|
| 2239 | } |
---|
| 2240 | return(maxpos); |
---|
| 2241 | } |
---|
| 2242 | |
---|
| 2243 | static proc sortintvec (intvec w) |
---|
| 2244 | "USAGE: sortintvec(v); v intvec |
---|
| 2245 | RETURN: intvec, the entries of v are ordered in an ascending way |
---|
| 2246 | NOTE: called from ellipticNF" |
---|
| 2247 | { |
---|
| 2248 | int j,k,stop; |
---|
| 2249 | intvec v=w[1]; |
---|
| 2250 | for (j=2;j<=size(w);j++) |
---|
| 2251 | { |
---|
| 2252 | k=1; |
---|
| 2253 | stop=0; |
---|
| 2254 | while ((k<=size(v)) and (stop==0)) |
---|
| 2255 | { |
---|
| 2256 | if (v[k]<w[j]) |
---|
| 2257 | { |
---|
| 2258 | k++; |
---|
| 2259 | } |
---|
[7e8485] | 2260 | else |
---|
[b0732eb] | 2261 | { |
---|
| 2262 | stop=1; |
---|
| 2263 | } |
---|
| 2264 | } |
---|
| 2265 | if (k==size(v)+1) |
---|
| 2266 | { |
---|
| 2267 | v=v,w[j]; |
---|
| 2268 | } |
---|
| 2269 | else |
---|
| 2270 | { |
---|
| 2271 | if (k==1) |
---|
| 2272 | { |
---|
| 2273 | v=w[j],v; |
---|
| 2274 | } |
---|
| 2275 | else |
---|
| 2276 | { |
---|
| 2277 | v=v[1..k-1],w[j],v[k..size(v)]; |
---|
| 2278 | } |
---|
| 2279 | } |
---|
| 2280 | } |
---|
| 2281 | return(v); |
---|
| 2282 | } |
---|
| 2283 | |
---|
| 2284 | static proc sortlistbyintvec (list L,intvec w) |
---|
| 2285 | "USAGE: sortlistbyintvec(L,w); L list, w intvec |
---|
| 2286 | RETURN: list, the entries of L are ordered such that the corresponding reordering of |
---|
| 2287 | w would order w in an ascending way |
---|
| 2288 | NOTE: called from ellipticNF" |
---|
| 2289 | { |
---|
| 2290 | int j,k,stop; |
---|
| 2291 | intvec v=w[1]; |
---|
| 2292 | list LL=L[1]; |
---|
| 2293 | for (j=2;j<=size(w);j++) |
---|
| 2294 | { |
---|
| 2295 | k=1; |
---|
| 2296 | stop=0; |
---|
| 2297 | while ((k<=size(v)) and (stop==0)) |
---|
| 2298 | { |
---|
| 2299 | if (v[k]<w[j]) |
---|
| 2300 | { |
---|
| 2301 | k++; |
---|
| 2302 | } |
---|
[7e8485] | 2303 | else |
---|
[b0732eb] | 2304 | { |
---|
| 2305 | stop=1; |
---|
| 2306 | } |
---|
| 2307 | } |
---|
| 2308 | if (k==size(v)+1) |
---|
| 2309 | { |
---|
| 2310 | v=v,w[j]; |
---|
| 2311 | LL=insert(LL,L[j],size(LL)); |
---|
| 2312 | } |
---|
| 2313 | else |
---|
| 2314 | { |
---|
| 2315 | if (k==1) |
---|
| 2316 | { |
---|
| 2317 | v=w[j],v; |
---|
| 2318 | LL=insert(LL,L[j]); |
---|
| 2319 | } |
---|
| 2320 | else |
---|
| 2321 | { |
---|
| 2322 | v=v[1..k-1],w[j],v[k..size(v)]; |
---|
| 2323 | LL=insert(LL,L[j],k-1); |
---|
| 2324 | } |
---|
| 2325 | } |
---|
| 2326 | } |
---|
| 2327 | return(LL); |
---|
| 2328 | } |
---|
| 2329 | |
---|
| 2330 | static proc matrixtointmat (matrix MM) |
---|
| 2331 | "USAGE: matrixtointmat(v); MM matrix |
---|
| 2332 | ASSUME: MM is a matrix with only integers as entries |
---|
| 2333 | RETURN: intmat, the matrix MM has been transformed to type intmat |
---|
| 2334 | NOTE: called from ellipticNF" |
---|
| 2335 | { |
---|
| 2336 | intmat M[nrows(MM)][ncols(MM)]=M; |
---|
| 2337 | int i,j; |
---|
| 2338 | for (i=1;i<=nrows(M);i++) |
---|
| 2339 | { |
---|
| 2340 | for (j=1;j<=ncols(M);j++) |
---|
| 2341 | { |
---|
| 2342 | execute("M["+string(i)+","+string(j)+"]="+string(MM[i,j])+";"); |
---|
| 2343 | } |
---|
| 2344 | } |
---|
| 2345 | return(M); |
---|
| 2346 | } |
---|
| 2347 | |
---|
| 2348 | ////////////////////////////////////////////////////////////////////////////// |
---|
| 2349 | |
---|
| 2350 | static proc polygonToCoordinates (list points) |
---|
| 2351 | "USAGE: polygonToCoordinates(points); points list |
---|
[7e8485] | 2352 | ASSUME: points is a list of integer vectors each of size two describing the |
---|
| 2353 | marked points of a convex lattice polygon like the output of |
---|
[b0732eb] | 2354 | polygonDB |
---|
[7e8485] | 2355 | RETURN: list, the first entry is a string representing the coordinates |
---|
[b0732eb] | 2356 | corresponding to the latticpoints seperated by commata |
---|
[7e8485] | 2357 | the second entry is a list where the ith entry is a string |
---|
| 2358 | representing the coordinate of corresponding to the ith |
---|
| 2359 | lattice point the third entry is the latex format of the |
---|
[b0732eb] | 2360 | first entry |
---|
| 2361 | NOTE: the procedure is called by fan" |
---|
| 2362 | { |
---|
| 2363 | string coord; |
---|
| 2364 | list coords; |
---|
| 2365 | string latex; |
---|
| 2366 | for (int i=1;i<=size(points);i++) |
---|
| 2367 | { |
---|
| 2368 | coords[i]="u"+string(points[i][1])+string(points[i][2]); |
---|
| 2369 | coord=coord+coords[i]+","; |
---|
| 2370 | latex=latex+"u_{"+string(points[i][1])+string(points[i][2])+"},"; |
---|
| 2371 | } |
---|
| 2372 | coord=coord[1,size(coord)-1]; |
---|
| 2373 | latex=latex[1,size(latex)-1]; |
---|
| 2374 | return(list(coord,coords,latex)); |
---|
| 2375 | } |
---|
[7e8485] | 2376 | |
---|
| 2377 | static proc intmatAddFirstColumn (intmat M,string art) |
---|
| 2378 | "USAGE: intmatAddFirstColumn(M,art); M intmat, art string |
---|
| 2379 | ASSUME: - M is an integer matrix where a first column of 0's or 1's should be added |
---|
| 2380 | @* - art is one of the following strings: |
---|
| 2381 | @* + 'rays' : indicating that a first column of 0's should be added |
---|
| 2382 | @* + 'points' : indicating that a first column of 1's should be added |
---|
| 2383 | RETURN: intmat, a first column has been added to the matrix" |
---|
| 2384 | { |
---|
| 2385 | intmat N[nrows(M)][ncols(M)+1]; |
---|
| 2386 | int i,j; |
---|
| 2387 | for (i=1;i<=nrows(M);i++) |
---|
| 2388 | { |
---|
| 2389 | if (art=="rays") |
---|
| 2390 | { |
---|
| 2391 | N[i,1]=0; |
---|
| 2392 | } |
---|
| 2393 | else |
---|
| 2394 | { |
---|
| 2395 | N[i,1]=1; |
---|
| 2396 | } |
---|
| 2397 | for (j=1;j<=ncols(M);j++) |
---|
| 2398 | { |
---|
| 2399 | N[i,j+1]=M[i,j]; |
---|
| 2400 | } |
---|
| 2401 | } |
---|
| 2402 | return(N); |
---|
| 2403 | } |
---|
| 2404 | |
---|
| 2405 | |
---|
| 2406 | |
---|