%%%%%%%%%%%%%LATEX FILE%%%%%%%%%%%%%%%%%%%%%% %\documentstyle[11pt,epsf,psfrag]{article} \documentstyle[11pt,epsf]{article} % Load the AmSTeX blackboard-bold font \font\Bbb=msym10 scaled 1200 \newenvironment{example}{\begin{exm} \rm}{\end{exm}}{} \newtheorem{thm}{Theorem}[section] \newtheorem{prop}[thm]{Proposition} \newtheorem{defi}[thm]{Definition} \newtheorem{lema}[thm]{Lemma} \newtheorem{cor}[thm]{Corollary} \newtheorem{exm}[thm]{Example} \newtheorem{rem}[thm]{Remarks} \newcommand{\nota}{\noindent {\bf Note:}} \newcommand{\proof}{\noindent {\it Proof: }} \newcommand{\qed}{\vrule height4pt width4pt depth4pt} %\newcommand{\qed}{\begin{flushright}{\mbox{ $\Box$}}\end{flushright}\vspace{1ex}} %\newcommand{\qed}{\hfill{\mbox{ $\Box$} \\}} \newcommand{\ben}{\begin{equation}} % Begin Eqn Numbered \newcommand{\een}{\end{equation}} \newcommand{\bean}{\begin{eqnarray}} % Begin Eqnarray Numbered \newcommand{\eean}{\end{eqnarray}} \newcommand{\T}{{\cal T}} \newcommand{\e}{\epsilon} \newcommand{\w}{\omega} \newcommand{\nat}{\mbox{\Bbb N}} \newcommand{\zed}{\mbox{\Bbb Z}} \newcommand{\real}{ {\mbox{\Bbb R}} } \newcommand{\rat}{{\mbox{\Bbb Q}}} \newcommand{\C}{{\mbox{\Bbb C}}} \newcommand{\toro}{{(\C^*)^n}} \newcommand{\projsp}{{\PP^{n-1}}} \newcommand{\grass}{{\G (k,n)}} \newcommand{\PP}{{\mbox{\Bbb P}}} \newcommand{\G}{{\mbox{\Bbb G}}} \newcommand{\ie}{{\it i.e.}} \newcommand{\K}{{\kappa}} \newcommand{\r}{{\bf R}} \newcommand{\A}{{\cal A}} \newcommand{\B}{{\cal B}} \newcommand{\p}{{\cal P}} \newcommand{\hyp}{{\Delta (2,n)}} \newcommand{\tntm}{T_{n-1} \times T_{m-1}} \begin{document} \input{psfig} \title{COMPUTING REGULAR TRIANGULATIONS \\OF POINT CONFIGURATIONS} \author{ Jes\'us de Loera} \maketitle \section{Introduction} {\bf PUNTOS} is a program to study regular triangulations and secondary polytopes of point configurations. The purpose of these notes is to discuss various aspects of the program. We start with a brief introduction to the mathematical concepts involved and the analysis of the algorithm. In the second section we discuss how to use the program and present several examples. In the final section we present some new computational results obtained and some possible directions of improvement. Let $\A=\{a_1,\dots,a_n\}$ denote an affine set $n$ of points in $\real ^k$ which spans an affine hyperplane. A {\em triangulation} of $\A$ is a triangulation of the $k-1$ dimensional polytope $P= conv (\A)$ with vertices in $\A$. We say that a triangulation $T$ is {\em regular} if it can be constructed as follows: Choose numbers $\lambda_1,\lambda_2,\dots,\lambda_n$ and let $W=conv(\{(a_1,\lambda_1),..,(a_n,\lambda_n)\}) \subset \real^{k+1}$. If $S'=\{(a_{i_1},\lambda_{i_1}),\dots,(a_{i_k},\lambda_{i_k})\}$ is a facet of $W$ in the lower hull of $W$ (i.e. the last component of the outward normal of its supporting hyperplane is negative) then $S=\{a_{i_1} ,\dots,a_{i_k}\}$ is a simplex of the triangulation $T$. The most common strategies to triangulate a point configuration such as pulling and placing are known to provide regular triangulations. Similarly the widely studied Delaunay triangulations belong to the class of regular triangulations. An interesting property of regular triangulations was discovered by Gelfand Kapranov and Zelevinskii (see \cite{oneGKZ}). The lattice of regular triangulations and subdivisions of a point configuration is polytopal (see \cite{BIFIST}). In particular there exists a canonically assigned polytope $\sum(\A)$, the {\em secondary polytope}, whose vertices correspond to the regular triangulations of the point configurations $\A$. We concentrate now in the structure of the one skeleton of $\sum(\A)$. The program PUNTOS generates the vertices and edges of the secondary polytope. The following result characterizing when two regular triangulations are adjacent will be of extreme importance for us (see \cite{GKZ}). A collection of points $Z$ is a {\em circuit} if any proper subset $Z'$ is affinely independent but $Z$ is affinely dependent (we refer the reader to \cite{OMB} for a discussion of circuits and Oriented Matroids). We observe that up to real scalar multiple there is a unique real affine relation among the elements of $Z$. We can thus decompose $Z$ into those elements $Z_+$ that appear with positive coefficient in the unique affine relation, and $Z_{-}=Z -Z_+$. Given a circuit $Z \subset \A$ we define two triangulations $t_{+}(Z)$ and $t_{-}(Z)$ of $conv(Z)$ as follows: $t_{+}(Z)$ (and respectively $t_{-}(Z)$) as the collection of simplices $\{ Z - \{ p \} \vert p \in Z_{+}\}$. \begin{defi} Let $T$ be a triangulation of $\A$, $Z$ a circuit. We say that $T$ is supported on $Z$ if the following conditions are satisfied: \begin{enumerate} \item The vertices of $T$ that belong to the $conv(Z)$ belong to $Z$. \item The polytope $conv(Z)$ is the union of faces of simplices of $T$. \item Let $\Delta$ be a maximal dimensional simplex of $t_{+}(Z)$ (similar things applies for $t_{-}(Z)$). If there exists $\Pi \subset \A-Z$ such that $conv(\Delta \cup \Pi)$ is a maximal dimensional simplex of $T$, then for all other maximal dimensional simplex $\Delta'$ , of the triangulation $t_{+}(Z)$ of $conv(Z)$, $conv(\Delta' \cup \Pi)$ is a simplex of $T$. \end{enumerate} \end{defi} We observe that if a triangulation $T$ is supported on the circuit $Z$, then $T$ induces a triangulation $t_{+}(Z)$. We obtain a new triangulation of $\A$, $flip_Z (T)$ as follows: replace the simplices of the form $conv(\Delta \cup \Pi)$, $\Delta$ simplex of $t_{+}(Z)$, with the simplices of the form $conv(\Delta' \cup \Pi)$ with $\Delta'$ simplex of $t_{-} (Z)$. This provide us with the required notion of adjacency for the following important definition: \begin{defi} The graph of triangulations of the point configuration $\G_{\A}$ is the graph whose vertices are the distinct triangulations of $\A$ and two of its vertices are adjacent if the two triangulations are supported in a common circuit. \end{defi} The following theorem of Gelfand Kapranov and Zelevinskii shows that the one skeleton of the secondary polytope of $\A$ is contained in a connected component of $\G_{\A}$. We call this connected component the {\em regular component} of $\G_{\A}$. \begin{thm} Let $T$ and $T'$ be two regular triangulations of the point configuration $\A$. The vertices $\phi_T$, $\phi_{T'}$ of the secondary polytope $\sum(\A)$ corresponding to $T$ and $T'$ are joined by and edge if and only if there exists a circuit $Z$ of $\A$ that supports both $T$ and $T'$ and $flip_Z(T)=T'$. \end{thm} It is important to observe that even when $T$ is a regular triangulation, the modified triangulation $flip_Z(T)=T'$, obtained from a circuit may not be regular. Thus the regular component of $\G_A$ may contain also some non regular elements. We have to check the regularity of triangulations obtained from the circuit flipping. For these we are based on the following result (see \cite{Lee} page 449). We remark that the algorithmic corroboration of the above criteria is equivalent to checking the feasibility of certain system of linear inequalities. \begin{thm} Suppose $T:=\{S_1,\dots,S_r\}$ is a subdivision of the point configuration $\A$. Let $\bar{\A}$ be the Gale transform of $\A$. Then $T$ is a regular subdivision if and only if $\cap _{i=1}^{r} relint(cone(\bar{\A}-\bar{S_i})) \not= \emptyset$. \end{thm} With the above adjacency structure we can device different ways to enumerate or generate the vertices of the secondary polytope. The objects of our interest constitutes a subgraph of the graph of $\G_{\A}$ determined by the circuits and we have to state a rule to visit all the vertices of this subgraph. This rule should avoid counting the same vertex twice. The algorithm used in PUNTOS is a breadth-first search of the regularity component of $\G_{\A}$. This is implemented in the subroutine {\em grafo}. Our algorithm needs to do four basic tasks: \begin{enumerate} \item Produce the circuits of the point configuration $\A$ (This is equivalent to computing the Oriented Matroid associated with the point configuration $\A$). Performed with the subroutine {\em circo}. \item Compute an initial regular triangulation that will be the root of the generation (or enumeration) of the triangulations from the flips. (In our implementation this is performed with the subroutine {\em Mac\_input} and the aid of MACAULAY.) \item For a given triangulation $T$ determine those circuits on which $T$ is supported (This is done with the subroutine {\em link\_and\_boundary\_check}). \item Check regularity of the triangulations generated. \end{enumerate} Using steps (1) and (3) one can determine the neighbors of a triangulation. The breadth-first search has linear complexity on the number of vertices and edges of the graph we are searching. The above operations determine the complexity of the algorithm. The algorithm is clearly output sensitive. \begin{thm} The above algorithm computes the vertices of the regular component of the graph of triangulations of a point configuration with $n$ vertices inside $\zed^d$ in time $O(dn^{2d+4}log(n)+Vol(\A)\vert{\cal C}\vert +(n-d)Vol(\A)(n-d-1)^3L \vert T \vert)$. Where $\vert T \vert$ denotes the number of triangulations in the regular component of $\G_A$, $\vert {\cal C} \vert$ is the number of circuits in $\A$, $Vol(\A)$ is the normalized volume of the convex hull of $\A$ and $L$ is the size of the coordinates of the points. \end{thm} \proof We analyze first the complexity of computing the circuits. The point configuration $\A$ is represented by a $d+1$ by $n$ matrix $P$. We denote by $Q$ a $n-d-1$ by $n$ matrix whose rows form a basis for the kernel of $P$. The circuits of $\A$ can be identified with the following signed vectors (The nonzero entries labeled the circuit $Z$ and the sign of an entry indicates whether it belongs to $Z_+$ or $Z_-$). We denote by $\chi (\lambda_1,...,\lambda_{d+1})$ the sign of the determinant of the submatrix of $Q$ whose columns are indexed by $\lambda_1,...,\lambda_{n-d-1}$. $$ C_\mu =\left( \begin{array}{c} \chi(\mu_1,\dots,\mu_d,1) \\ \chi(\mu_1,\dots,\mu_d,2) \\ \vdots \\ \chi(\mu_1,\dots,\mu_d,n) \end{array} \right) $$ The vector $C_\mu$ is has only $0,1,-1$ as entries. The label $\mu$ is an ordered $n-d-2$ subset of $1,\dots,n$. We have to use several times the different maximal minors of the matrix $Q$. They appear with a distinct sign depending of the reordering of the list $\mu_1,\dots,\mu_d,i$ (determined by the parity of the permutation). We need to compute the $n \choose {d+1}$ sign-determinants as fast as possible. For this we use some basic identities of tensor algebra (we are grateful to Bernd Sturmfels for suggesting this). Suppose $b$ is a list of $m$ vectors in $\real^n$. Let $B$ be a matrix of this list relative to the standard basis, in the sense that $b_j=\sum e_i A_{ij}$ for $j \in 1,\dots,m$. Then for each increasing list $k$ of $q$ elements in $1,\dots,m$. we have: $$b_{k_1} \wedge b_{k_2} \wedge \dots \wedge b_{k_q}=\sum_h e_{h_1} \wedge \dots \wedge e_{h_q} det(B(h,k))$$ Where the sum runs over all increasing lists $h$ of $q$ elements in $1,\dots,n$ and $B(h,k)$ is the $q$ by $q$ submatrix of $B$ whose rows are labeled by $h$ and the columns by $k$. In particular the $n \choose {d+1}$ vector of all the $d+1$ by $d+1$ determinants can be computed applying the above relation first to two, then three,etc, of the $d+1$ vectors. When we wedge an j-vector (an element of $\wedge^j \real^n$) with a one-vector (an element of $\real^n$) we use the distributivity of the wedge product and thus we have $n \choose j$ times $n$ multiplications. >From the multiplication we obtain a $j+1$-vector $W$. This $j+1$-vector can be finally expressed in terms of the standard basis of $\wedge^{j+1} \real^n$ for this we have to permute the $e_{i_1} \wedge \dots \wedge e_{i_{j+1}}$ so that the indices are in increasing order. The wedge product has an alternating property and thus the entries of $W$ are changed in signed according to the parity of the permutation performed. We observe that for each of the multiplications we performed a sorting of $e_{i_1} \wedge \dots \wedge e_{i_{j+1}}$ which amounts for time $(j+1) log(j+1)$. It is easy to see that the complexity of computing all the $d+1$ by $d+1$ determinants is bounded by $O(dn^{d+4}log(n))$. Finally we see that to compute the circuits we must form $O(n^d)$ of the sign vectors $C_\mu$. This gives the bound $O(dn^{2d+4}log(n))$ in the computation of the circuits. The computation of a seed regular triangulation can be done at the time complexity of computing a convex hull (for instance Delaunay triangulations are regular). It is well known that for a set of $n$ points in $\real^{d+1}$ its convex hull can be computed in $O(nlog(n)+n^{\lfloor (d+1)/2 \rfloor})$. This is in fact optimal in the worst case (see \cite{Edels}). The complexity then is so far dominated by the computation of the circuits. When we check for a circuit to be supported in a triangulation we essentially check the inclusion of the circuit elements inside the maximal simplices of the triangulation. The complexity of the procedure determining the support is thus related to the number of simplices of the triangulation. The {\em normalized volume} $Vol(\A)$ of a $d$-dimensionalpoint configuration $\A$ is given by the unique volume form on the affine hull of $\A$ which is normalized by requiring that the non-zero simplex volumes of $d$-simplices supported in the configuration $\A$ are relatively prime integers. The configuration $\A$ can be triangulated in the largest case by $Vol(\A)$ many simplices (when all simplices have normalized unit volume). For each circuit inside the configuration we check for support. If ${\cal C}$ denotes the set of circuits we must do then $Vol(\A) \vert {\cal C} \vert$ inclusion checks. The containment of two sets of size $d$ can be done on $d$ comparisons. This part of the process takes then $O(dVol(\A) \vert {\cal C} \vert)$. Finally when we do a flip operation based on a circuit we may change from a regular into a nonregular triangulation. After the vertices of the regular component have been generated we check which are regular. Theorem 1.4 tells how to set up a linear system of inequalities to corroborate regularity on a triangulation. Suppose $S:=\{S_1,\dots,S_r\}$ is a triangulation of the point configuration $\A$. Let $\bar{\A}$ be the Gale transform of $\A$. Then $S$ is a regular triangulation if and only if $\cap _{i=1}^{r} relint(cone(\bar{\A}-\bar{S_i})) \not= \emptyset$. This is an intersection of $\vert S \vert$ simplicial cones inside $\real^{n-d-1}$. For each cone its interior is defined by a system of $n-d$ inequalities. We have thus a total of $(n-d)Vol(\A)$ inequalities in $n-d-1$ variables defining the intersection. The best algorithmic bounds for the above feasibility problem can be achieved using interior point methods (see \cite{GrLoSc}). Given the above system the emptiness of the cone intersection can be decided by the basic Ellipsoid method. The number of basic arithmetic operations needed is $O((n-d)Vol(\A)(n-d-1)^3L)$ where $L$ is the size of the input coefficients. The complexity of the regularity check is then $O((n-d)Vol(\A)(n-d-1)^3L) \vert T \vert)$ \qed In many cases of interest we receive more information than just the point configuration. If we know the group of symmetries $\Gamma$ of the point configuration $\A$ we can contract the one skeleton of $\sum (\A)$ to obtain a quotient graph $\G_{\A}/\Gamma$ with smaller number of vertices. We have now a vertex for each orbit of $\Gamma$ of its action on the set of regular triangulations of $\A$. Two of these vertices are joined if corresponding representatives are joined. We do a breadth-first search on the smaller quotient graph. As before we start we a seed triangulation and we know the neighbors of a triangulation at every stage. Everytime we get a new triangulation $T$ we check whether its orbit has been visited already (we produce new triangulations by the adjacency rule we discussed). The whole orbit of $T$ can then be added to the set of triangulations or simply store $T$ as the representative of an orbit. \section{Tutorial} PUNTOS consists of MAPLE and MACAULAY procedures. In what follows we assume basic familiarity with Unix and Maple (we tried to make the use of MACAULAY invisible for the user). PUNTOS was written on a unix-based SUN system. The program has a main file {\em puntos} and several auxiliary files {\em makeup, matriz,matrizaux and macinput} that are called at some points of the process. finally there is this file {\em manual.ps}. There are only four basic functions inside the program: {\em grafo, GKZ\_embedding} and {\em circo}. We present several examples next. \begin{itemize} \item {\begin{itemize} \item{\bf grafo} -- Computes the regular component of the $\G_{\A}$ an arbitrary point configuration. If the group of symmetries of $\A$ is used, grafo generates the quotient graph of the regular component. \item{\em Parameters:} A matrix $A$ encoding the point configuration. The name of a file where to store the list of triangulations, even non-regular triangulations if any appears. The triangulations are given as simplicial complexes. As a third optional parameter is the name of a file that contains a list of lists containing the symmetries of the point configuration. \item{\em Synopsis:} Starting with an initial regular triangulation, the generation of the graph is done in the form of a breadth-first search. The subroutine is called by writing $grafo(A,filename,group)$. The result is stored in the list {\em triangulations} and the graph structure {\em skeleton}. We can also call grafo with an optional third parameter which is a name for the file that contains the symmetries of the point configuration. The graph computed in this case is the quotient graph of the graph of bistellar flips that contain the one skeleton of $\sum(\A)$. \end{itemize}} \item {\begin{itemize} \item{\bf GKZ\_embedding} -- Computes the Gelfand-Kapranov-Zelevinskii embedding of the vertices of the secondary polytope of a point configuration. \item{\em Parameters:} A matrix $A$ encoding the point configuration. An optional second parameter the name of a file where the output can be directed. \item{\em Synopsis:} You have to invoque the command grafo before using this command. A set of vectors is produced. The regular triangulations are stored in the set {\em retriangus} as simplicial complexes. The output is similar to PORTA readable input. The command is invoqued as $GKZ\_embedding(A,filename)$. Where the second optional parameter is the name of a file where the output is directed. On its abscence the result is printed to the screen. \end{itemize}} \item {\begin{itemize} \item{\bf circo} -- Computes cocircuits of a point configuration \item{\em Parameters:} A matrix $A$ encoding the point configuration. \item{\em Synopsis:} The result is stored as the list $cocircuits$. The function is called by $circo(A)$ \end{itemize}} \item {\begin{itemize} \item{\bf orbita} -- Computes the orbit of a triangulation under the action of a group. \item{\em Parameters:} A triangulation $T$ given as a set of sets. It uses the group symmetry\_moves which was read in advanced. \item{\em Synopsis:} The result is set of simplicial complexes. \end{itemize}} \end{itemize} We present first a simple calculation of the triangulations of a hexagon. We first load the package PUNTOS: \begin{verbatim} gothics% maple |\^/| Maple V Release 2 (Cornell University) ._|\| |/|_. Copyright (c) 1981-1992 by the University of Waterloo. \ MAPLE / All rights reserved. MAPLE is a registered trademark of <____ ____> Waterloo Maple Software. | Type ? for help. >read `puntos.m`; \end{verbatim} Now we can start working. We must start by introducing a point configuration. In this case we get it from the file hex.points (depending of your terminal and maple version at this point you may not see a prompt but it is not necessary). \begin{verbatim} > read(hexagon); [ 1 1 1 1 1 1 ] [ ] U := [ 1 2 2 1 0 0 ] [ ] [ 0 1 2 2 1 0 ] \end{verbatim} Now we want to compute the 1-skeleton of the secondary polytope of the point configuration $U$. We invoque the subroutine grafo. the symbols $!$ that appear next indicate that the seed triangulation is being computed with MACAULAY. we next see the seed triangulation appear and the indication that the circuits of the point configuration are being computed (using the procedure circo). \begin{verbatim} > grafo(U,example); ! ! ! ! ! ! ! ! ! THIS IS THE SEED TRIANGULATION FROM WHICH WE WILL GROW THE SECONDARY, {{4, 5, 6}, {1, 2, 6}, {3, 4, 6}, {2, 3, 6}} I STARTED TO COMPUTE THE CIRCUITS OF THE POINT CONFIGURATION I have computed, 1 I have computed, 2 I have computed, 3 I have computed, 4 I have computed, 5 I have computed, 6 I have computed, 7 I have computed, 8 I have computed, 9 I have computed, 10 I have computed, 11 I have computed, 12 I have computed, 13 I have computed, 14 I have computed, 15 \end{verbatim} The next message may seem confusing but it has a meaning only when we use the procedure circo to compute cocircuits (In that case the cocircuits of a point configuration represent the facets of the convex hull). \begin{verbatim} this polytope has, 0, facets I FINISH COMPUTING THE CIRCUITS WITH A TOTAL OF:, 15 \end{verbatim} Now the most interesting part is the generation of the actual triangulations. At every step we are informed of how many of the vertices we have expanded and how many are on the queue to be visited. \begin{verbatim} I AM GOING TO COMPUTE THE SECONDARY POLYTOPE 4 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 3 elements 6 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 4 elements 8 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 5 elements 9 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 5 elements 10 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 5 elements 11 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 5 elements 12 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 5 elements 13 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 5 elements 14 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 5 elements 14 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 4 elements 14 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 3 elements 14 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 2 elements 14 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 1 elements 14 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 0 elements We have generated, 14, distinct triangulations using bistellar operations. We still have to check which of these triangulations are regular All the triangulations produced so far are stored in the file designated We have analyzed, 1, of the, 14, vertices for regularity We have analyzed, 2, of the, 14, vertices for regularity We have analyzed, 3, of the, 14, vertices for regularity We have analyzed, 4, of the, 14, vertices for regularity We have analyzed, 5, of the, 14, vertices for regularity We have analyzed, 6, of the, 14, vertices for regularity We have analyzed, 7, of the, 14, vertices for regularity We have analyzed, 8, of the, 14, vertices for regularity We have analyzed, 9, of the, 14, vertices for regularity We have analyzed, 10, of the, 14, vertices for regularity We have analyzed, 11, of the, 14, vertices for regularity We have analyzed, 12, of the, 14, vertices for regularity We have analyzed, 13, of the, 14, vertices for regularity We have analyzed, 14, of the, 14, vertices for regularity THE SECONDARY POLYTOPE HAS, 14, VERTICES. The regular triangulations are in the variable retriangus IF YOU WISH YOU MAY APPLY FURTHER ANALYSIS TO THE VERTICES recall that all the triangulations are stored in the variable triangulations and the variable retriangus contains those that are regular. using the procedure GKZ_embedding you can print the Gelfand-Kapranov-Zelevinskii embedding of the triangulations Keep in mind that if you used the symmetries of the point configuration you have stored in the variables triangulations and retriangus representatives for the distinct triangulations. \end{verbatim} In this particular case this is a three dimensional polytope with 14 vertices. We can know more about its graph using some of the graph theoretical tools available in MAPLE. We use now some of these commands. We have stored the graph in the global variable skeleton. \begin{verbatim} >degreeseq(skeleton); [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3] >diameter(skeleton); 4 \end{verbatim} In small cases,having a picture of the skeleton may be useful. You can obtain a Postscript file with a drawing of the skeleton. To do this invoque the following commands (the actual figure uses a whole page and the vertices are labeled). \begin{verbatim} >interface(plotdevice=postscript); >interface(plotoutput= myfile); >draw(skeleton); \end{verbatim} \begin{figure}[htbp] \begin{center} \leavevmode \hbox{% \epsfysize=4.5in \epsffile{fig1.ps}} \end{center} \caption{The one skeleton of the secondary polytope} \end{figure} %\centerline{\psfig{figure=fig1.ps,height=3in}} Now we are going to see another example. We will compute explicit equations for the facets of the secondary polytope of the three dimensional cube. We will use PUNTOS to produce the vertices of the secondary polytope and then use PORTA ( a polyhedral manipulation package) to compute the convex hull. \begin{verbatim} |\^/| Maple V Release 2 (Cornell University) ._|\| |/|_. Copyright (c) 1981-1992 by the University of Waterloo. \ MAPLE / All rights reserved. MAPLE is a registered trademark of <____ ____> Waterloo Maple Software. | Type ? for help. > read `puntos.m`; > read(trescubo); [ 2 0 2 2 0 2 0 0 ] [ ] [ 2 0 2 0 2 0 2 0 ] cubo := [ ] [ 2 0 0 2 2 0 0 2 ] [ ] [ 1 1 1 1 1 1 1 1 ] > grafo(cubo,example); \end{verbatim} We see that the result is (after approximately 7 minutes in a Sparc station 10) 74 regular triangulations. After the computation is finished we can obtain the coordinates of the triangulations. We use the command $GKZ\_embedding$ (This in fact printed in a single column). \begin{verbatim} > GKZ_embedding(cubo); > DIM= 8 CONV_SECTION [8, 24, 24, 48, 32, 16, 32, 8] [24, 24, 8, 24, 40, 40, 24, 8] [24, 8, 16, 8, 32, 48, 24, 32] [16, 24, 48, 16, 24, 16, 8, 40] [24, 24, 8, 40, 24, 24, 40, 8] [16, 24, 48, 24, 16, 8, 16, 40] [24, 8, 32, 8, 16, 32, 24, 48] [32, 16, 8, 8, 32, 48, 24, 24] [8, 24, 32, 48, 24, 8, 32, 16] [8, 32, 32, 48, 32, 8, 24, 8] [24, 8, 32, 16, 8, 24, 32, 48] [32, 8, 8, 8, 24, 48, 32, 32] [16, 8, 16, 16, 40, 48, 24, 24] [8, 32, 48, 32, 32, 8, 8, 24] [24, 8, 8, 32, 16, 32, 48, 24] [8, 40, 40, 40, 40, 8, 8, 8] [32, 16, 32, 8, 8, 24, 24, 48] [48, 32, 8, 8, 16, 32, 24, 24] [8, 8, 24, 40, 24, 24, 40, 24] [8, 24, 48, 32, 24, 8, 16, 32] [40, 48, 24, 16, 24, 16, 8, 16] [16, 24, 24, 48, 16, 8, 40, 16] [16, 32, 48, 24, 24, 8, 8, 32] [48, 40, 16, 16, 8, 16, 24, 24] [48, 32, 16, 8, 8, 24, 24, 32] [32, 48, 24, 32, 24, 8, 16, 8] [32, 16, 8, 32, 8, 24, 48, 24] [8, 24, 32, 24, 48, 32, 8, 16] [48, 32, 8, 16, 8, 24, 32, 24] [8, 24, 24, 32, 48, 32, 16, 8] [8, 8, 40, 24, 24, 24, 24, 40] [8, 32, 32, 32, 48, 24, 8, 8] [8, 16, 24, 24, 48, 40, 16, 16] [16, 16, 16, 16, 48, 48, 16, 16] [8, 24, 48, 24, 32, 16, 8, 32] [48, 24, 8, 8, 8, 32, 32, 32] [8, 8, 24, 24, 40, 40, 24, 24] [40, 40, 8, 24, 24, 24, 24, 8] [40, 8, 8, 8, 8, 40, 40, 40] [32, 48, 24, 24, 32, 16, 8, 8] [16, 16, 16, 48, 16, 16, 48, 16] [24, 8, 16, 32, 8, 24, 48, 32] [16, 16, 48, 16, 16, 16, 16, 48] [48, 48, 16, 16, 16, 16, 16, 16] [40, 48, 16, 24, 24, 16, 16, 8] [32, 8, 24, 8, 8, 32, 32, 48] [24, 48, 32, 32, 32, 8, 8, 8] [16, 24, 16, 48, 24, 16, 40, 8] [40, 48, 24, 24, 16, 8, 16, 16] [24, 16, 8, 40, 16, 24, 48, 16] [16, 32, 24, 24, 48, 32, 8, 8] [24, 16, 16, 40, 8, 16, 48, 24] [32, 8, 8, 24, 8, 32, 48, 32] [24, 24, 24, 8, 40, 40, 8, 24] [24, 16, 40, 16, 8, 16, 24, 48] [24, 24, 40, 8, 24, 24, 8, 40] [24, 16, 40, 8, 16, 24, 16, 48] [48, 40, 16, 8, 16, 24, 16, 24] [16, 32, 24, 48, 24, 8, 32, 8] [8, 16, 24, 48, 24, 16, 40, 16] [24, 24, 24, 40, 8, 8, 40, 24] [16, 8, 16, 40, 16, 24, 48, 24] [40, 40, 24, 8, 24, 24, 8, 24] [16, 24, 24, 16, 48, 40, 8, 16] [24, 16, 16, 8, 40, 48, 16, 24] [16, 24, 16, 24, 48, 40, 16, 8] [16, 8, 40, 16, 16, 24, 24, 48] [40, 40, 24, 24, 8, 8, 24, 24] [24, 8, 8, 16, 32, 48, 32, 24] [32, 48, 32, 24, 24, 8, 8, 16] [48, 40, 8, 16, 16, 24, 24, 16] [8, 16, 48, 24, 24, 16, 16, 40] [24, 24, 40, 24, 8, 8, 24, 40] [24, 16, 8, 16, 40, 48, 24, 16] END \end{verbatim} Next we compute the convex hull of the given points. These points define a four dimensional polytope with 74 vertices and 22 facets (corresponding to the coarsest regular subdivisions of the cube) whose equations are listed below. \begin{verbatim} ( 1) +x4-x5+x6-x7 == 0 ( 2) +x3 -x5+x6 -x8 == 0 ( 3) +x1-x2 +x5-x6 == 0 ( 4) +x2 +x5 +x7+x8 == 96 ( 1) - x5 -x7-x8 <= -48 ( 12) +x8 <= 48 ( 2) -2x5+x6-x7-x8 <= -48 ( 13) +x7 <= 48 ( 3) - x5 -x7 <= -32 ( 14) +x6 <= 48 ( 4) - x5 -x8 <= -32 ( 15) + x5 <= 48 ( 5) - x5+x6-x7-x8 <= -32 ( 16) + x5-x6 +x8 <= 48 ( 6) - x5 <= -8 ( 17) + x5-x6+x7 <= 48 ( 7) -x6 <= -8 ( 18) + x5 +x8 <= 64 ( 8) -x7 <= -8 ( 19) + x5 +x7 <= 64 ( 9) -x8 <= -8 ( 20) + x5-x6+x7+x8 <= 64 ( 10) - x5+x6-x7 <= -8 ( 21) + x5 +x7+x8 <= 88 ( 11) - x5+x6 -x8 <= -8 ( 22) +2x5-x6+x7+x8 <= 88 \ N P \ U O F \ M O I A \ B F N C \ E T E \ R S T \ S \ --------------- 1 | : 8 2 | : 8 3 | : 18 4 | : 18 5 | : 18 6 | : 16 7 | : 16 8 | : 16 9 | : 16 10 | : 16 11 | : 16 12 | : 8 13 | : 8 14 | : 8 15 | : 8 16 | : 8 17 | : 8 18 | : 18 19 | : 18 20 | : 18 21 | : 16 22 | : 16 \end{verbatim} Now we include an example where the symmetries are used to speed up the computation. This is the calculation of the secondary polytope of the product of two triangles. This example was originally computed by Postnikov (see chapter seven of \cite{GKZbook}). The group $S_3 \times S_3$ acts on the vertices of the polytope $T_2 \times T_2$. We show next how the file containing the symmetries should look. the notation for the permutations is functional not as cycle decomposition. The group has to be listed completely (including the identity) not only by generators. In our example we have 36 elements in the group which must receive the name symmetry\_moves. \begin{verbatim} symmetry_moves := [[1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 3, 2, 4, 6, 5, 7, 9, 8], [2, 1, 3, 5, 4, 6, 8, 7, 9], [2, 3, 1, 5, 6, 4, 8, 9, 7], [3, 1, 2, 6, 4, 5, 9, 7, 8], [3, 2, 1, 6, 5, 4, 9, 8, 7], [1, 2, 3, 7, 8, 9, 4, 5, 6], [1, 3, 2, 7, 9, 8, 4, 6, 5], [2, 1, 3, 8, 7, 9, 5, 4, 6], [2, 3, 1, 8, 9, 7, 5, 6, 4], [3, 1, 2, 9, 7, 8, 6, 4, 5], [3, 2, 1, 9, 8, 7, 6, 5, 4], [4, 5, 6, 1, 2, 3, 7, 8, 9], [4, 6, 5, 1, 3, 2, 7, 9, 8], [5, 4, 6, 2, 1, 3, 8, 7, 9], [5, 6, 4, 2, 3, 1, 8, 9, 7], [6, 4, 5, 3, 1, 2, 9, 7, 8], [6, 5, 4, 3, 2, 1, 9, 8, 7], [4, 5, 6, 7, 8, 9, 1, 2, 3], [4, 6, 5, 7, 9, 8, 1, 3, 2], [5, 4, 6, 8, 7, 9, 2, 1, 3], [5, 6, 4, 8, 9, 7, 2, 3, 1], [6, 4, 5, 9, 7, 8, 3, 1, 2], [6, 5, 4, 9, 8, 7, 3, 2, 1], [7, 8, 9, 1, 2, 3, 4, 5, 6], [7, 9, 8, 1, 3, 2, 4, 6, 5], [8, 7, 9, 2, 1, 3, 5, 4, 6], [8, 9, 7, 2, 3, 1, 5, 6, 4], [9, 7, 8, 3, 1, 2, 6, 4, 5], [9, 8, 7, 3, 2, 1, 6, 5, 4], [7, 8, 9, 4, 5, 6, 1, 2, 3], [7, 9, 8, 4, 6, 5, 1, 3, 2], [8, 7, 9, 5, 4, 6, 2, 1, 3], [8, 9, 7, 5, 6, 4, 2, 3, 1], [9, 7, 8, 6, 4, 5, 3, 1, 2], [9, 8, 7, 6, 5, 4, 3, 2, 1]]: \end{verbatim} We can now use {\em grafo} with a third parameter. The same calculation could be performed without a group of symmetries but instead of a few minutes it takes almost half an hour. We first generate the point configuration using a small auxiliary procedure. Notice that we have the points inside the hyperplane $x_5=1$. The matrix containing the point configuration is $TnTm$. \begin{verbatim} > TnXTm(2,2); this polytope has, 9, faces of dimension, 0 this polytope has, 18, faces of dimension, 1 this polytope has, 15, faces of dimension, 2 this polytope has, 6, faces of dimension, 3 this polytope has, 1, faces of dimension, 4 [ 0 0 0 1 1 1 0 0 0 ] [ ] [ 0 0 0 0 0 0 1 1 1 ] [ ] [ 0 1 0 0 1 0 0 1 0 ] [ ] [ 0 0 1 0 0 1 0 0 1 ] [ ] [ 1 1 1 1 1 1 1 1 1 ] > >grafo(TnTm,example,symt2t2); READING THE SYMMETRY GROUP OF THE CONFIGURATION ! ! ! ! ! ! ! ! THIS IS THE SEED TRIANGULATION FROM WHICH WE WILL GROW THE SECONDARY, {{2, 3, 4, 5, 7}, {3, 6, 7, 8, 9}, {1, 2, 3, 4, 7}, {3, 5, 6, 7, 8}, {2, 3, 5, 7, 8}, {3, 4, 5, 6, 7}} I STARTED TO COMPUTE THE CIRCUITS OF THE POINT CONFIGURATION \end{verbatim} After a few minutes we can see the results. There are five distinct triangulations modulo the symmetries of $S_3 \times S_3$. The quotient graph of the regular component of $\G_A$ is stored in the variable skeleton. We can see the adjacencies by calling the MAPLE command $ends(skeleton)$. \begin{verbatim} I AM GOING TO COMPUTE THE SECONDARY POLYTOPE 3 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 2 elements 4 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 2 elements 4 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 1 elements 5 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 1 elements 5 vertices have been produced so far The set of those vertices waiting for the determination of its neighbors has 0 elements We have generated, 5, distinct triangulations using bistellar operations. We still have to check which of these triangulations are regular All the triangulations produced so far are stored in the file designated We have analyzed, 1, of the, 5, vertices for regularity We have analyzed, 2, of the, 5, vertices for regularity We have analyzed, 3, of the, 5, vertices for regularity We have analyzed, 4, of the, 5, vertices for regularity We have analyzed, 5, of the, 5, vertices for regularity THE SECONDARY POLYTOPE HAS, 108, VERTICES. The representatives of the regular triangulations are in the variable retriangus IF YOU WISH YOU MAY APPLY FURTHER ANALYSIS TO THE VERTICES recall that all the triangulations are stored in the variable triangulations and the variable retriangus contains those that are regular. using the procedure GKZ_embedding you can print the Gelfand-Kapranov-Zelevinskii embedding of the triangulations Keep in mind that if you used the symmetries of the point configuration you have stored in the variables triangulations and/or retriangus representatives for the distinct triangulations > ends(skeleton); {{3, 4}, {2, 3}, {4}, {2, 5}, {1, 2}, {1, 3}} > triangulations; [{{1, 2, 3, 4, 7}, {3, 6, 7, 8, 9}, {3, 5, 6, 7, 8}, {2, 3, 5, 7, 8}, {3, 4, 5, 6, 7}, {2, 3, 4, 5, 7}}, {{1, 2, 3, 4, 7}, {3, 5, 6, 7, 9}, {3, 5, 7, 8, 9} , {2, 3, 5, 7, 8}, {3, 4, 5, 6, 7}, {2, 3, 4, 5, 7}}, {{1, 2, 3, 4, 7}, {2, 3, 6, 7, 8}, {2, 3, 4, 6, 7}, {2, 5, 6, 7, 8}, {2, 4, 5, 6, 7}, {3, 6, 7, 8, 9}}, {{1, 2, 3, 4, 7}, {2, 4, 6, 7, 8}, {2, 3, 6, 7, 8}, {2, 3, 4, 6, 7}, {2, 4, 5, 6, 8}, {3, 6, 7, 8, 9}}, {{1, 3, 4, 5, 7}, {3, 5, 6, 7, 9}, {3, 5, 7, 8, 9}, {2 , 3, 5, 7, 8}, {3, 4, 5, 6, 7}, {1, 2, 3, 5, 7}}] > \end{verbatim} The five triangulations appear in the order they are labeled inside the list triangulations. It is very easy now from the representatives and the group to generate the whole set of 108 regular triangulations. We can do this using an internal command of PUNTOS called {\em orbita}. This procedure computes the orbit of an element provided the group has been previously read. In this case the file {\em symt2t2} is already in the system. \begin{verbatim} > all_reg_trian:={}: > for cell in regtriangus do > all_reg_trian:=all_reg_trian union orbita(cell): > od: bytes used=22024004, alloc=1507052, time=58.78 > nops(all_reg_trian); 108 >retriangus:=all_reg_trian: \end{verbatim} As we did in the case of the cube we can now easily compute explicit equations for the facets of the secondary polytope of $T_2 \times T_2$. We use PORTA to calculate the equations from the GKZ coordinates of the 108 triangulations. We present a complete description of the 30 facet defining inequalities. \begin{verbatim} >GKZ_embedding(TnTm); DIM= 9 CONV_SECTION [2, 5, 3, 2, 2, 6, 6, 3, 1] [3, 5, 2, 1, 3, 6, 6, 2, 2] [3, 1, 6, 2, 6, 2, 5, 3, 2] [6, 2, 2, 1, 6, 3, 3, 2, 5] [1, 3, 6, 3, 4, 3, 6, 3, 1] [2, 2, 6, 6, 3, 1, 2, 5, 3] [2, 5, 3, 6, 3, 1, 2, 2, 6] [2, 6, 2, 5, 3, 2, 3, 1, 6] [1, 6, 3, 5, 3, 2, 4, 1, 5] [1, 4, 5, 5, 1, 4, 4, 5, 1] [3, 6, 1, 2, 3, 5, 5, 1, 4] [2, 6, 2, 6, 1, 3, 2, 3, 5] [6, 1, 3, 3, 5, 2, 1, 4, 5] [1, 4, 5, 4, 5, 1, 5, 1, 4] [4, 1, 5, 5, 4, 1, 1, 5, 4] [5, 1, 4, 4, 5, 1, 1, 4, 5] [3, 2, 5, 6, 2, 2, 1, 6, 3] [2, 2, 6, 5, 2, 3, 3, 6, 1] [2, 3, 5, 2, 6, 2, 6, 1, 3] [1, 3, 6, 3, 5, 2, 6, 2, 2] [3, 2, 5, 1, 6, 3, 6, 2, 2] [6, 2, 2, 3, 5, 2, 1, 3, 6] [2, 2, 6, 2, 6, 2, 6, 2, 2] [4, 1, 5, 1, 5, 4, 5, 4, 1] [2, 2, 6, 3, 6, 1, 5, 2, 3] [5, 3, 2, 3, 1, 6, 2, 6, 2] [2, 2, 6, 2, 5, 3, 6, 3, 1] [5, 2, 3, 3, 6, 1, 2, 2, 6] [2, 6, 2, 6, 2, 2, 2, 2, 6] [5, 4, 1, 4, 1, 5, 1, 5, 4] [5, 4, 1, 1, 5, 4, 4, 1, 5] [6, 2, 2, 3, 2, 5, 1, 6, 3] [6, 1, 3, 2, 6, 2, 2, 3, 5] [4, 5, 1, 1, 4, 5, 5, 1, 4] [1, 3, 6, 6, 2, 2, 3, 5, 2] [2, 6, 2, 2, 3, 5, 6, 1, 3] [6, 3, 1, 2, 5, 3, 2, 2, 6] [5, 1, 4, 1, 4, 5, 4, 5, 1] [3, 6, 1, 5, 2, 3, 2, 2, 6] [5, 3, 2, 4, 1, 5, 1, 6, 3] [6, 1, 3, 2, 3, 5, 2, 6, 2] [3, 1, 6, 5, 4, 1, 2, 5, 3] [3, 1, 6, 5, 3, 2, 2, 6, 2] [3, 2, 5, 1, 5, 4, 6, 3, 1] [1, 6, 3, 6, 2, 2, 3, 2, 5] [3, 5, 2, 1, 4, 5, 6, 1, 3] [1, 6, 3, 3, 2, 5, 6, 2, 2] [2, 3, 5, 5, 1, 4, 3, 6, 1] [6, 2, 2, 2, 6, 2, 2, 2, 6] [5, 4, 1, 3, 1, 6, 2, 5, 3] [6, 2, 2, 2, 2, 6, 2, 6, 2] [4, 1, 5, 1, 6, 3, 5, 3, 2] [2, 2, 6, 6, 2, 2, 2, 6, 2] [5, 1, 4, 3, 6, 1, 2, 3, 5] [2, 6, 2, 2, 2, 6, 6, 2, 2] [4, 5, 1, 1, 3, 6, 5, 2, 3] [1, 6, 3, 3, 3, 4, 6, 1, 3] [5, 3, 2, 2, 6, 2, 3, 1, 6] [2, 6, 2, 3, 1, 6, 5, 3, 2] [1, 4, 5, 6, 1, 3, 3, 5, 2] [1, 5, 4, 4, 1, 5, 5, 4, 1] [4, 5, 1, 5, 2, 3, 1, 3, 6] [1, 5, 4, 3, 2, 5, 6, 3, 1] [1, 5, 4, 6, 3, 1, 3, 2, 5] [6, 3, 1, 2, 2, 6, 2, 5, 3] [5, 4, 1, 2, 5, 3, 3, 1, 6] [3, 6, 1, 2, 2, 6, 5, 2, 3] [5, 1, 4, 2, 3, 5, 3, 6, 1] [6, 1, 3, 1, 6, 3, 3, 3, 4] [4, 1, 5, 5, 3, 2, 1, 6, 3] [3, 1, 6, 3, 6, 1, 4, 3, 3] [1, 4, 5, 3, 5, 2, 6, 1, 3] [4, 5, 1, 5, 1, 4, 1, 4, 5] [5, 3, 2, 1, 6, 3, 4, 1, 5] [1, 6, 3, 6, 1, 3, 3, 3, 4] [2, 3, 5, 3, 6, 1, 5, 1, 4] [1, 3, 6, 6, 3, 1, 3, 4, 3] [1, 3, 6, 4, 5, 1, 5, 2, 3] [6, 3, 1, 3, 4, 3, 1, 3, 6] [3, 2, 5, 6, 3, 1, 1, 5, 4] [3, 6, 1, 4, 3, 3, 3, 1, 6] [3, 5, 2, 6, 1, 3, 1, 4, 5] [6, 1, 3, 3, 3, 4, 1, 6, 3] [1, 6, 3, 4, 1, 5, 5, 3, 2] [3, 1, 6, 4, 3, 3, 3, 6, 1] [5, 2, 3, 2, 2, 6, 3, 6, 1] [2, 3, 5, 6, 1, 3, 2, 6, 2] [3, 6, 1, 5, 1, 4, 2, 3, 5] [6, 3, 1, 1, 3, 6, 3, 4, 3] [6, 1, 3, 1, 4, 5, 3, 5, 2] [3, 6, 1, 3, 1, 6, 4, 3, 3] [6, 3, 1, 1, 5, 4, 3, 2, 5] [4, 3, 3, 3, 1, 6, 3, 6, 1] [5, 2, 3, 4, 5, 1, 1, 3, 6] [3, 3, 4, 1, 6, 3, 6, 1, 3] [2, 5, 3, 5, 4, 1, 3, 1, 6] [3, 4, 3, 1, 3, 6, 6, 3, 1] [3, 5, 2, 6, 2, 2, 1, 3, 6] [4, 3, 3, 3, 6, 1, 3, 1, 6] [2, 5, 3, 3, 1, 6, 5, 4, 1] [3, 4, 3, 6, 3, 1, 1, 3, 6] [5, 2, 3, 1, 3, 6, 4, 5, 1] [3, 3, 4, 6, 1, 3, 1, 6, 3] [6, 3, 1, 3, 2, 5, 1, 5, 4] [1, 3, 6, 5, 2, 3, 4, 5, 1] [1, 5, 4, 5, 4, 1, 4, 1, 5] [6, 2, 2, 1, 3, 6, 3, 5, 2] [3, 1, 6, 2, 5, 3, 5, 4, 1] END >quit; DIM = 9 VALID 3 1 6 2 5 3 5 4 1 INEQUALITIES_SECTION ( 1) +x3 +x6-x7-x8 == 0 ( 2) +x2+x3-x4 -x7 == 0 ( 3) +x4+x5+x6-x7-x8-x9 == 0 ( 4) +x1+x2+x3-x4-x5-x6 == 0 ( 5) +x7+x8+x9 == 10 ( 1) -x5-x6-x8-x9 <= -11 ( 16) +x6-x8 <= 4 ( 2) -x5-x6-x8 <= -6 ( 17) +x5 -x9 <= 4 ( 3) -x5-x6 -x9 <= -6 ( 18) +x9 <= 6 ( 4) -x5 -x8-x9 <= -6 ( 19) +x8 <= 6 ( 5) -x6-x8-x9 <= -6 ( 20) +x6 <= 6 ( 6) -x5-x6 <= -4 ( 21) +x5 <= 6 ( 7) -x5 -x8 <= -4 ( 22) +x8+x9 <= 9 ( 8) -x6 -x9 <= -4 ( 23) +x6 +x9 <= 9 ( 9) -x8-x9 <= -4 ( 24) +x5 +x8 <= 9 ( 10) -x5 <= -1 ( 25) +x5+x6 <= 9 ( 11) -x6 <= -1 ( 26) +x6+x8+x9 <= 14 ( 12) -x8 <= -1 ( 27) +x5 +x8+x9 <= 14 ( 13) -x9 <= -1 ( 28) +x5+x6 +x9 <= 14 ( 14) -x5 +x9 <= 4 ( 29) +x5+x6+x8 <= 14 ( 15) -x6+x8 <= 4 ( 30) +x5+x6+x8+x9 <= 16 \end{verbatim} \section{ Results} In this section we include a few new discoveries obtained using PUNTOS. From the beginning of the theory of regular triangulations a point configuration that has received a lot of attention is the set of vertices of the product of two simplices $\tntm$. The secondary polytope of the unimodular configuration $\tntm$ has dimension $(n-1)(m-1)$. Very little is known about $\sum(\tntm)$. We recommend chapter seven of \cite{GKZbook} for a presentation of results. We add modestly here to the knowledge of these polytopes with a few more data about $\sum(T_2 \times T_3)$ and $\sum(T_2 \times T_4)$ and $\sum(T_3 \times T_3)$. \begin{prop} \begin{itemize} \item The secondary polytope of $T_2 \times T_3$ has $4488$ vertices. Up to $S_3 \times S_4$ symmetry $T_2 \times T_3$ has only $35$ distinct regular triangulations. \item The secondary polytope of $T_2 \times T_4$ has, up to $S_3 \times S_5$ symmetry, 530 distinct regular triangulations. Its secondary polytope has 376200 vertices. \item The secondary polytope of $T_3 \times T_3$ has at least $3714$ distinct (up to $S_4 \times S_4$ symmetry) regular triangulations. \end{itemize} \end{prop} \proof The first two results were obtained using the program PUNTOS (the actual triangulations for $T_2 \times T_3$ appear in the appendix). For the third result we recall (see cite{Bernd1} and ) that another description of $\sum(\tntm)$ is as the Newton polytope of the product of all minors of an $m \times n$ matrix of indeterminates. In the particular case of $T_3 \times T_3$ we have a $4 \times 4$ matrix which has 16 one by one minors, 36 $2 \times 2$ minors, 16 $3 \times 3$ minors and one $4 \times 4$ minor. Multiplying these determinants and expanding the product to read all the monomial coefficients is not an option. Nevertheless we can use a probabilistic approach. Let $f(x_{11},\dots,x_{44})$ be the polynomial obtained from the multiplication of all the above minors. We can use an auxiliary parameter $t$ and for each $\omega$ in $\rat^{16}$ we can define $f_\omega =f(t^{\omega_11}x_{11},\dots,t^{\omega_44}x_{44})$. We observe that $f_\omega$ can be seen as a polynomial in $t$ with coefficients in $\C [ x_{11}, \dots,x_{44}] $. Its leading coefficient is a polynomial that we call the {\em initial form}. The distinct initial forms as $\omega$ ranges over $\rat^{16}$ are in one-to-one correspondence with the faces of the Newton polytope of $f$. Furthermore when the initial form is a monomial it corresponds to a vertex. We observe that since $f$ factors as the product of determinants its initial forms factors as the product of the initial forms of each of the minors. What we do is randomly assign values to $\omega$ and compute the initial forms of the minors. If all of them are monomials we have reached a monomial of $f$ which represents a vertex. The exponent vector of the initial form of $f$ can be thought as an invariant associated with the triangulations of $\tntm$. Two isomorphic triangulations will have the same exponent vector up to a permutation. We can do a rough classification of the randomly generated vectors by considering two vectors equal when the sorting of its entries gives the same lists. A repetition of the above process for a million times produced precisely 3714 distinct vectors. \qed One well known point configuration due to its relations to Veronese embeddings of projective spaces and Viro's construction of real algebraic curves with prescribed topology is the two dimensional configuration $V_d$ of points with coordinates $(i,j,k)$ such that $i+j+k=d$ for a fixed value $d$. We present a computational analysis of the secondary polytope of $V_3$. We include the list of triangulations in the appendix. \begin{prop} The secondary polytope of $V_3$ has 1166 vertices. The point configuration $V_3$ has 213 distinct regular triangulations modulo the symmetry of $S_3$. \end{prop} The triangulations of the $d$-dimensional cube have received a lot of attention because of its application to the computation of fixed points (see \cite{Todd} and \cite{ToddLev}). Here we present a small contribution to the structure of triangulations of the $d$-cube (details will appear elsewhere). \begin{thm} The four dimensional cube has a non-regular triangulation into simplices of unit volume. In particular this induces a non-regular triangulation for cubes of arbitrary dimension. \end{thm} \proof We work with the following coordinates for the four cube (the ith column is the ith vertex of the point configuration). \begin{verbatim} [ 2 0 2 2 2 0 2 2 2 0 0 0 2 0 0 0 ] [ ] [ 2 0 2 2 0 2 2 0 0 2 2 0 0 2 0 0 ] [ ] [ 2 0 2 0 2 2 0 2 0 2 0 2 0 0 2 0 ] [ ] [ 2 0 0 2 2 2 0 0 2 0 2 2 0 0 0 2 ] [ ] [ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ] \end{verbatim} The proposed simplicial complex is \begin{verbatim} {{7, 9, 10, 11, 13}, {7, 10, 11, 13, 14}, {10, 11, 13, 14, 16}, {2, 10, 13, 15, 16}, {2, 10, 13, 14, 16}, {9, 10, 11, 13, 16}, {8, 10, 13, 15, 16}, {8, 10, 12, 15, 16}, {1, 5, 6, 7, 10}, {1, 3, 5, 7, 10}, {5, 7, 9, 10, 13}, {5, 6, 7, 10, 11}, {5, 7, 9, 10, 11}, {4, 5, 7, 9, 11}, {5, 6, 10, 11, 12}, {1, 5, 6, 7, 11}, {1, 4, 5, 7, 11}, {5, 10, 11, 12, 16}, {5, 8, 10, 12, 16}, {5, 9, 10, 11, 16}, {5, 9, 10, 13, 16}, {5, 8, 10, 13, 16}, {3, 5, 8, 10, 13}, {3, 5, 7, 10, 13}}: \end{verbatim} It is enough to check that the simplices form a simplicial complex (no patological intersections) and the regularity condition stated in theorem 1.4 is violated in this case. We omitt the details at this point. \qed We close this section with a quick view to some other possible algorithms that we hope to implement in the near future. In our generation of regular triangulations we would like to minimize the storage of triangulations. An idea suggested by N. Takayama and T.Masada (see \cite{Masa}) is to use the so called {\em reverse search} enumeration procedure. This was first presented in \cite{Fuku}. We assign to each vertex of the secondary a label that characterize it uniquely. We use the Gelfand-Kapranov- Zelevinskii vector of a triangulation $\Delta$ : $\sum _{i=1}^n (\sum \{vol(\sigma) \vert \sigma \in \Delta \})e_i$. Given two regular triangulations $\Delta$ and $\Delta'$ we define $\Delta > \Delta'$ if and only if the GKZ vector of $\Delta$ is lexicographically bigger than $\Delta'$. The main fact to be consider is that distinct regular triangulations have distinct GKZ vectors. Using the graph and the order on the vertices of the secondary graph we observe that there is a set of local maxima. Starting with any vertex we can follow the an increasing path of vertices until we reach a vertex all whose neighbors have smaller GKZ vector. This defines a spanning forest in the secondary graph polytope. The trees of the forest are rooted on the maximal points. Now we can start from each root an enumeration of the vertices of the secondary polytope. We do this in a depth first search. The entire information about the search tree need not be stored. The memory space complexity can be reduced to the size of the input triangulation. \section{Appendix} We present all the details of triangulations anounced before. We start with the product of two simplices. The following matrix has as columns the vertices of $T_2 \times T_3$. This is a five dimensional polytope with 12 vertices, 30 edges, 34 two dimensional faces, 21 three dimensional faces and 7 facets. \begin{verbatim} [ 0 0 0 0 1 1 1 1 0 0 0 0 ] [ ] [ 0 0 0 0 0 0 0 0 1 1 1 1 ] [ ] [ 0 1 0 0 0 1 0 0 0 1 0 0 ] [ ] [ 0 0 1 0 0 0 1 0 0 0 1 0 ] [ ] [ 0 0 0 1 0 0 0 1 0 0 0 1 ] [ ] [ 1 1 1 1 1 1 1 1 1 1 1 1 ] {{2,3,4,5,6,9},{4,8,9,10,11,12},{1,2,3,4,5,9}, {2,3,4,6,9,10},{4,7,8,9,10,11},{3,4,7,9,10,11}, {4,6,7,8,9,10},{3,4,6,7,9,10},{4,5,6,7,8,9}, {3,4,5,6,7,9}} {{4,8,9,10,11,12},{1,2,3,4,5,9},{4,7,8,9,10,11}, {3,4,7,9,10,11},{4,6,7,8,9,10},{4,5,6,7,8,9}, {2,4,5,6,7,9},{2,3,4,5,7,9},{2,3,4,7,9,10}, {2,4,6,7,9,10}} {{2,3,4,5,6,9},{1,2,3,4,5,9},{2,3,4,6,9,10}, {3,4,7,9,10,11},{4,6,7,8,9,10},{3,4,6,7,9,10}, {4,5,6,7,8,9},{3,4,5,6,7,9},{4,7,9,10,11,12}, {4,7,8,9,10,12}} {{4,8,9,10,11,12},{1,2,3,4,5,9},{4,7,8,9,10,11}, {3,4,7,9,10,11},{4,5,7,8,9,10},{3,4,5,7,9,10}, {4,5,6,7,8,10},{3,4,5,6,7,10},{2,3,4,5,9,10}, {2,3,4,5,6,10}} {{4,8,9,10,11,12},{4,7,8,9,10,11},{3,4,7,9,10,11}, {4,6,7,8,9,10},{4,5,6,7,8,9},{2,4,5,6,7,9}, {2,3,4,7,9,10},{2,4,6,7,9,10},{1,2,4,5,7,9}, {1,2,3,4,7,9}} {{4,8,9,10,11,12},{1,2,3,4,5,9},{4,7,8,9,10,11}, {3,4,7,9,10,11},{2,3,4,5,7,9},{2,3,4,7,9,10}, {4,5,7,8,9,10},{4,5,6,7,8,10},{2,4,5,6,7,10}, {2,4,5,7,9,10}} {{1,2,3,4,5,9},{3,4,7,9,10,11},{4,6,7,8,9,10}, {4,5,6,7,8,9},{2,4,5,6,7,9},{2,3,4,5,7,9}, {2,3,4,7,9,10},{2,4,6,7,9,10},{4,7,9,10,11,12}, {4,7,8,9,10,12}} {{4,8,9,10,11,12},{1,2,3,4,5,9},{4,7,8,9,10,11}, {3,4,7,9,10,11},{2,3,4,5,7,9},{2,3,4,7,9,10}, {2,6,7,8,9,10},{2,5,6,7,8,9},{2,4,5,7,8,9}, {2,4,7,8,9,10}} {{4,8,9,10,11,12},{4,7,8,9,10,11},{3,4,7,9,10,11}, {2,3,4,7,9,10},{1,2,4,5,7,9},{1,2,3,4,7,9}, {2,6,7,8,9,10},{2,5,6,7,8,9},{2,4,5,7,8,9}, {2,4,7,8,9,10}} {{4,8,9,10,11,12},{1,2,3,4,5,9},{4,7,8,9,10,11}, {3,4,7,9,10,11},{2,3,4,5,7,9},{2,3,4,7,9,10}, {2,4,5,7,8,9},{2,4,7,8,9,10},{2,5,6,7,8,10}, {2,5,7,8,9,10}} {{4,8,9,10,11,12},{1,2,3,4,5,9},{2,6,7,8,9,10}, {2,5,6,7,8,9},{2,3,4,5,8,9},{2,3,5,7,8,9}, {3,4,8,9,10,11},{2,3,7,8,9,10},{3,7,8,9,10,11}, {2,3,4,8,9,10}} {{1,2,3,4,5,9},{3,4,7,9,10,11},{2,3,4,5,7,9}, {2,3,4,7,9,10},{4,7,9,10,11,12},{4,7,8,9,10,12}, {2,6,7,8,9,10},{2,5,6,7,8,9},{2,4,5,7,8,9}, {2,4,7,8,9,10}} {{4,8,9,10,11,12},{4,7,8,9,10,11},{3,4,7,9,10,11}, {2,3,4,7,9,10},{1,2,4,5,7,9},{1,2,3,4,7,9}, {2,4,5,7,8,9},{2,4,7,8,9,10},{2,5,6,7,8,10}, {2,5,7,8,9,10}} {{4,8,9,10,11,12},{4,7,8,9,10,11},{1,2,4,5,7,9}, {1,2,3,4,7,9},{2,6,7,8,9,10},{2,5,6,7,8,9}, {2,4,5,7,8,9},{2,4,7,8,9,10},{2,4,7,9,10,11}, {2,3,4,7,9,11}} {{4,8,9,10,11,12},{4,7,8,9,10,11},{3,4,7,9,10,11}, {2,3,4,7,9,10},{1,2,3,4,7,9},{2,6,7,8,9,10}, {2,5,6,7,8,9},{2,4,7,8,9,10},{1,2,5,7,8,9}, {1,2,4,7,8,9}} {{3,4,7,9,10,11},{2,3,4,7,9,10},{4,7,9,10,11,12}, {4,7,8,9,10,12},{1,2,4,5,7,9},{1,2,3,4,7,9}, {2,6,7,8,9,10},{2,5,6,7,8,9},{2,4,5,7,8,9}, {2,4,7,8,9,10}} {{4,8,9,10,11,12},{1,2,3,4,5,9},{2,5,6,7,8,10}, {2,5,7,8,9,10},{2,3,4,5,8,9},{2,3,5,7,8,9}, {3,4,8,9,10,11},{2,3,7,8,9,10},{3,7,8,9,10,11}, {2,3,4,8,9,10}} {{4,8,9,10,11,12},{2,6,7,8,9,10},{2,5,6,7,8,9}, {2,3,5,7,8,9},{3,4,8,9,10,11},{2,3,7,8,9,10}, {3,7,8,9,10,11},{2,3,4,8,9,10},{1,2,3,5,8,9}, {1,2,3,4,8,9}} {{4,8,9,10,11,12},{1,2,3,4,5,9},{2,3,4,5,8,9}, {3,4,8,9,10,11},{3,7,8,9,10,11},{2,3,4,8,9,10}, {2,3,5,6,8,9},{3,5,6,7,8,9},{3,6,7,8,9,10}, {2,3,6,8,9,10}} {{4,8,9,10,11,12},{1,2,3,4,5,9},{2,6,7,8,9,10}, {2,5,6,7,8,9},{2,3,4,5,8,9},{2,3,5,7,8,9}, {2,7,8,9,10,11},{2,4,8,9,10,11},{2,3,4,8,9,11}, {2,3,7,8,9,11}} {{4,8,9,10,11,12},{2,6,7,8,9,10},{2,5,6,7,8,9}, {2,3,5,7,8,9},{1,2,3,5,8,9},{1,2,3,4,8,9}, {2,7,8,9,10,11},{2,4,8,9,10,11},{2,3,4,8,9,11}, {2,3,7,8,9,11}} {{4,8,9,10,11,12},{1,2,3,4,5,9},{2,5,6,7,8,10}, {2,5,7,8,9,10},{2,3,4,5,8,9},{2,3,5,7,8,9}, {2,7,8,9,10,11},{2,4,8,9,10,11},{2,3,4,8,9,11}, {2,3,7,8,9,11}} {{4,8,9,10,11,12},{1,2,3,4,5,9},{2,3,4,5,7,9}, {2,6,7,8,9,10},{2,5,6,7,8,9},{2,4,5,7,8,9}, {2,3,4,7,9,11},{2,7,8,9,10,11},{2,4,8,9,10,11}, {2,4,7,8,9,11}} {{4,8,9,10,11,12},{1,2,3,4,5,9},{2,3,4,5,8,9}, {3,4,8,9,10,11},{3,7,8,9,10,11},{2,3,4,8,9,10}, {3,5,7,8,9,10},{3,5,6,7,8,10},{2,3,5,8,9,10}, {2,3,5,6,8,10}} {{4,8,9,10,11,12},{3,4,8,9,10,11},{3,7,8,9,10,11}, {2,3,4,8,9,10},{1,2,3,5,8,9},{1,2,3,4,8,9}, {2,3,5,6,8,9},{3,5,6,7,8,9},{3,6,7,8,9,10}, {2,3,6,8,9,10}} {{2,6,7,8,9,10},{2,5,6,7,8,9},{2,3,5,7,8,9}, {1,2,3,5,8,9},{1,2,3,4,8,9},{2,7,8,9,10,11}, {2,3,4,8,9,11},{2,3,7,8,9,11},{2,8,9,10,11,12}, {2,4,8,9,11,12}} {{4,8,9,10,11,12},{4,7,8,9,10,11},{1,2,3,4,7,9}, {2,6,7,8,9,10},{2,5,6,7,8,9},{2,4,7,8,9,10}, {2,4,7,9,10,11},{2,3,4,7,9,11},{1,2,5,7,8,9}, {1,2,4,7,8,9}} {{3,4,7,9,10,11},{2,3,4,7,9,10},{4,7,9,10,11,12}, {4,7,8,9,10,12},{1,2,3,4,7,9},{2,6,7,8,9,10}, {2,5,6,7,8,9},{2,4,7,8,9,10},{1,2,5,7,8,9}, {1,2,4,7,8,9}} {{4,8,9,10,11,12},{4,7,8,9,10,11},{3,4,7,9,10,11}, {2,3,4,7,9,10},{1,2,3,4,7,9},{2,4,7,8,9,10}, {2,5,6,7,8,10},{2,5,7,8,9,10},{1,2,5,7,8,9}, {1,2,4,7,8,9}} {{4,8,9,10,11,12},{4,7,8,9,10,11},{2,6,7,8,9,10}, {2,5,6,7,8,9},{2,4,7,8,9,10},{2,4,7,9,10,11}, {1,2,5,7,8,9},{1,2,4,7,8,9},{1,2,4,7,9,11}, {1,2,3,4,7,11}} {{3,4,7,9,10,11},{4,6,7,8,9,10},{4,5,6,7,8,9}, {2,4,5,6,7,9},{2,3,4,7,9,10},{2,4,6,7,9,10}, {4,7,9,10,11,12},{4,7,8,9,10,12},{1,2,4,5,7,9}, {1,2,3,4,7,9}} {{3,4,7,9,10,11},{2,3,4,7,9,10},{4,7,9,10,11,12}, {4,7,8,9,10,12},{4,5,7,8,9,10},{4,5,6,7,8,10}, {1,2,4,5,7,9},{1,2,3,4,7,9},{2,4,5,6,7,10}, {2,4,5,7,9,10}} {{4,8,9,10,11,12},{4,7,8,9,10,11},{3,4,7,9,10,11}, {2,3,4,7,9,10},{4,5,7,8,9,10},{4,5,6,7,8,10}, {1,2,4,5,7,9},{1,2,3,4,7,9},{2,4,5,6,7,10}, {2,4,5,7,9,10}} {{4,8,9,10,11,12},{4,7,8,9,10,11},{1,2,4,5,7,9}, {1,2,3,4,7,9},{2,4,5,7,8,9},{2,4,7,8,9,10}, {2,5,6,7,8,10},{2,5,7,8,9,10},{2,4,7,9,10,11}, {2,3,4,7,9,11}} {{4,8,9,10,11,12},{1,2,3,4,5,9},{4,7,8,9,10,11}, {2,3,4,5,7,9},{2,4,5,7,8,9},{2,4,7,8,9,10}, {2,5,6,7,8,10},{2,5,7,8,9,10},{2,4,7,9,10,11}, {2,3,4,7,9,11}} \end{verbatim} The Veronese configuration of degree three has 213 distinct triangulations. The point of the configuration are (in order of labeling) $$(0,0,3),(0,1,2),(0,2,1),(0,3,0),(1,0,2),(1,1,1),(1,2,0),(2,0,1),(2,1,0),(3,0,0)$$ {\small $\{\{8,9,10\},\{1,2,5\},\{2,3,5\},\{3,4,5\},\{5,6,8\},\{4,5,6\},\{7,8,9\}, \{6,7,8\},\{4,6,7\}\}$ $\{\{8,9,10\},\{1,2,5\},\{5,6,8\},\{4,5,6\},\{7,8,9\},\{6,7,8\},\{4,6,7\}, \{2,4,5\}\}$ $\{\{8,9,10\},\{1,2,5\},\{2,3,5\},\{3,4,5\},\{5,6,8\},\{4,5,6\},\{4,6,7\}, \{6,8,9\},\{6,7,9\}\}$ $\{\{8,9,10\},\{1,2,5\},\{2,3,5\},\{3,4,5\},\{5,6,8\},\{4,5,6\},\{7,8,9\}, \{4,6,8\},\{4,7,8\}\}$ $\{\{8,9,10\},\{1,2,5\},\{2,3,5\},\{3,4,5\},\{7,8,9\},\{5,7,8\},\{4,5,7\}\}$ $\{\{1,2,5\},\{2,3,5\},\{3,4,5\},\{5,6,8\},\{4,5,6\},\{6,7,8\},\{4,6,7\}, \{7,8,10\}\}$ $\{\{8,9,10\},\{1,2,5\},\{2,3,5\},\{5,6,8\},\{7,8,9\},\{6,7,8\},\{4,6,7\}, \{3,4,6\},\{3,5,6\}\}$ $\{\{8,9,10\},\{3,4,5\},\{5,6,8\},\{4,5,6\},\{7,8,9\},\{6,7,8\},\{4,6,7\}, \{1,3,5\}\}$ $\{\{8,9,10\},\{1,2,5\},\{5,6,8\},\{4,5,6\},\{4,6,7\},\{2,4,5\},\{6,8,9\}, \{6,7,9\}\}$ $\{\{8,9,10\},\{1,2,5\},\{5,6,8\},\{7,8,9\},\{6,7,8\},\{4,6,7\},\{2,5,6\}, \{2,4,6\}\}$ $\{\{8,9,10\},\{5,6,8\},\{4,5,6\},\{7,8,9\},\{6,7,8\},\{4,6,7\},\{1,4,5\}\}$ $\{\{1,2,5\},\{5,6,8\},\{4,5,6\},\{6,7,8\},\{4,6,7\},\{2,4,5\},\{7,8,10\}\}$ $\{\{8,9,10\},\{1,2,5\},\{5,6,8\},\{4,5,6\},\{7,8,9\},\{2,4,5\},\{4,6,8\}, \{4,7,8\}\}$ $\{\{8,9,10\},\{1,2,5\},\{7,8,9\},\{2,4,5\},\{5,7,8\},\{4,5,7\}\}$ $\{\{8,9,10\},\{5,6,8\},\{4,5,6\},\{7,8,9\},\{4,6,8\},\{4,7,8\},\{1,4,5\}\}$ $\{\{8,9,10\},\{1,2,5\},\{5,6,8\},\{4,5,6\},\{2,4,5\},\{4,6,8\},\{4,8,9\}\}$ $\{\{8,9,10\},\{1,2,5\},\{5,6,8\},\{7,8,9\},\{4,6,8\},\{4,7,8\},\{2,5,6\}, \{2,4,6\}\}$ $\{\{8,9,10\},\{1,2,5\},\{7,8,9\},\{2,4,5\},\{4,7,8\},\{4,5,8\}\}$ $\{\{1,2,5\},\{5,6,8\},\{4,5,6\},\{2,4,5\},\{4,6,8\},\{4,7,8\},\{7,8,10\}\}$ $\{\{8,9,10\},\{1,2,5\},\{7,8,9\},\{4,7,8\},\{2,4,8\},\{2,5,8\}\}$ $\{\{1,2,5\},\{2,4,5\},\{4,7,8\},\{7,8,10\},\{4,5,8\}\}$ $\{\{8,9,10\},\{1,2,5\},\{2,3,5\},\{3,4,5\},\{7,8,9\},\{4,7,8\},\{4,5,8\}\}$ $\{\{8,9,10\},\{1,2,5\},\{2,4,5\},\{4,8,9\},\{4,5,8\}\}$ $\{\{8,9,10\},\{7,8,9\},\{4,7,8\},\{1,4,5\},\{4,5,8\}\}$ $\{\{8,9,10\},\{3,4,5\},\{7,8,9\},\{4,7,8\},\{1,3,5\},\{4,5,8\}\}$ $\{\{5,6,8\},\{4,5,6\},\{4,6,8\},\{4,7,8\},\{7,8,10\},\{1,4,5\}\}$ $\{\{8,9,10\},\{3,4,5\},\{5,6,8\},\{4,5,6\},\{7,8,9\},\{4,6,8\},\{4,7,8\}, \{1,3,5\}\}$ $\{\{8,9,10\},\{5,6,8\},\{4,5,6\},\{4,6,8\},\{1,4,5\},\{4,8,9\}\}$ $\{\{8,9,10\},\{5,6,8\},\{7,8,9\},\{4,6,8\},\{4,7,8\},\{1,5,6\},\{1,4,6\}\}$ $\{\{3,4,5\},\{5,6,8\},\{4,5,6\},\{4,6,8\},\{4,7,8\},\{7,8,10\},\{1,3,5\}\}$ $\{\{1,2,5\},\{2,4,5\},\{4,5,8\},\{4,8,10\}\}$ $\{\{8,9,10\},\{1,2,5\},\{4,8,9\},\{2,4,8\},\{2,5,8\}\}$ $\{\{8,9,10\},\{1,2,5\},\{4,6,8\},\{2,4,6\},\{4,8,9\},\{2,5,8\},\{2,6,8\}\}$ $\{\{8,9,10\},\{1,2,5\},\{4,8,9\},\{2,5,8\},\{3,4,8\},\{2,3,8\}\}$ $\{\{8,9,10\},\{1,2,5\},\{2,5,8\},\{2,4,9\},\{2,8,9\}\}$ $\{\{8,9,10\},\{4,8,9\},\{2,4,8\},\{1,2,8\}\}$ $\{\{1,2,5\},\{2,4,8\},\{2,5,8\},\{4,8,10\}\}$ $\{\{1,2,5\},\{4,6,8\},\{2,4,6\},\{2,5,8\},\{4,8,10\},\{2,6,8\}\}$ $\{\{1,2,5\},\{2,5,8\},\{4,8,10\},\{3,4,8\},\{2,3,8\}\}$ $\{\{2,4,8\},\{4,8,10\},\{1,2,8\}\}$ $\{\{1,2,5\},\{4,7,8\},\{7,8,10\},\{2,4,8\},\{2,5,8\}\}$ $\{\{1,2,5\},\{2,5,8\},\{2,4,10\},\{2,8,10\}\}$ $\{\{1,2,5\},\{4,7,8\},\{7,8,10\},\{2,5,8\},\{3,4,8\},\{2,3,8\}\}$ $\{\{1,2,5\},\{2,5,8\},\{2,3,8\},\{3,4,10\},\{3,8,10\}\}$ $\{\{1,2,5\},\{4,6,8\},\{3,4,6\},\{2,5,8\},\{4,8,10\},\{2,6,8\},\{2,3,6\}\}$ $\{\{4,8,10\},\{3,4,8\},\{2,3,8\},\{1,2,8\}\}$ $\{\{8,9,10\},\{1,2,5\},\{2,5,8\},\{2,3,8\},\{3,4,9\},\{3,8,9\}\}$ $\{\{8,9,10\},\{4,8,9\},\{3,4,8\},\{2,3,8\},\{1,2,8\}\}$ $\{\{8,9,10\},\{1,2,5\},\{4,6,8\},\{3,4,6\},\{4,8,9\},\{2,5,8\},\{2,6,8\}, \{2,3,6\}\}$ $\{\{8,9,10\},\{1,2,5\},\{7,8,9\},\{4,7,8\},\{2,5,8\},\{3,4,8\},\{2,3,8\}\}$ $\{\{1,2,5\},\{7,8,10\},\{2,5,8\},\{2,3,8\},\{3,4,7\},\{3,7,8\}\}$ $\{\{4,7,8\},\{7,8,10\},\{3,4,8\},\{2,3,8\},\{1,2,8\}\}$ $\{\{1,2,5\},\{4,6,8\},\{4,7,8\},\{7,8,10\},\{3,4,6\},\{2,5,8\},\{2,6,8\}, \{2,3,6\}\}$ $\{\{1,2,5\},\{2,3,5\},\{4,7,8\},\{7,8,10\},\{3,4,8\},\{3,5,8\}\}$ $\{\{8,9,10\},\{7,8,9\},\{4,7,8\},\{3,4,8\},\{2,3,8\},\{1,2,8\}\}$ $\{\{4,7,8\},\{7,8,10\},\{2,4,8\},\{1,2,8\}\}$ $\{\{4,7,8\},\{7,8,10\},\{3,4,8\},\{1,3,8\}\}$ $\{\{7,8,10\},\{2,3,8\},\{1,2,8\},\{3,4,7\},\{3,7,8\}\}$ $\{\{4,6,8\},\{4,7,8\},\{7,8,10\},\{3,4,6\},\{2,6,8\},\{1,2,8\},\{2,3,6\}\}$ $\{\{8,9,10\},\{7,8,9\},\{4,7,8\},\{2,4,8\},\{1,2,8\}\}$ $\{\{7,8,10\},\{1,2,8\},\{2,4,7\},\{2,7,8\}\}$ $\{\{4,6,8\},\{4,7,8\},\{7,8,10\},\{2,4,6\},\{2,6,8\},\{1,2,8\}\}$ $\{\{4,7,8\},\{7,8,10\},\{1,4,8\}\}$ $\{\{8,9,10\},\{7,8,9\},\{1,2,8\},\{2,4,7\},\{2,7,8\}\}$ $\{\{6,7,8\},\{7,8,10\},\{2,6,8\},\{1,2,8\},\{2,4,7\},\{2,6,7\}\}$ $\{\{8,9,10\},\{7,8,9\},\{1,2,8\},\{3,4,7\},\{2,7,8\},\{2,3,7\}\}$ $\{\{8,9,10\},\{7,8,9\},\{6,7,8\},\{2,6,8\},\{1,2,8\},\{2,4,7\},\{2,6,7\}\}$ $\{\{2,3,8\},\{1,2,8\},\{3,8,10\},\{3,4,7\},\{3,7,10\}\}$ $\{\{6,7,8\},\{7,8,10\},\{2,6,8\},\{1,2,8\},\{2,3,6\},\{3,4,7\},\{3,6,7\}\}$ $\{\{8,9,10\},\{7,8,9\},\{2,3,8\},\{1,2,8\},\{3,4,7\},\{3,7,8\}\}$ $\{\{7,8,10\},\{3,4,7\},\{3,7,8\},\{1,3,8\}\}$ $\{\{2,6,8\},\{1,2,8\},\{2,3,6\},\{3,4,7\},\{3,6,7\},\{6,8,10\},\{6,7,10\}\}$ $\{\{8,9,10\},\{7,8,9\},\{6,7,8\},\{2,6,8\},\{1,2,8\},\{2,3,6\},\{3,4,7\}, \{3,6,7\}\}$ $\{\{6,7,8\},\{7,8,10\},\{2,3,6\},\{3,4,7\},\{3,6,7\},\{1,6,8\},\{1,2,6\}\}$ $\{\{6,7,8\},\{4,6,7\},\{7,8,10\},\{3,4,6\},\{2,6,8\},\{1,2,8\},\{2,3,6\}\}$ $\{\{1,2,5\},\{6,7,8\},\{7,8,10\},\{2,5,8\},\{2,6,8\},\{2,3,6\},\{3,4,7\}, \{3,6,7\}\}$ $\{\{2,3,8\},\{1,2,8\},\{3,8,10\},\{3,4,7\},\{3,7,9\},\{3,9,10\}\}$ $\{\{3,8,10\},\{3,4,7\},\{1,3,8\},\{3,7,10\}\}$ $\{\{2,3,8\},\{1,2,8\},\{3,4,10\},\{3,8,10\}\}$ $\{\{1,2,8\},\{2,8,10\},\{3,4,10\},\{2,3,10\}\}$ $\{\{2,3,8\},\{1,2,8\},\{3,8,10\},\{3,4,9\},\{3,9,10\}\}$ $\{\{2,6,8\},\{1,2,8\},\{3,4,10\},\{2,3,6\},\{6,8,10\},\{3,6,10\}\}$ $\{\{3,4,10\},\{3,8,10\},\{1,3,8\}\}$ $\{\{3,4,10\},\{1,3,10\}\}$ $\{\{3,4,10\},\{6,8,10\},\{1,6,8\},\{3,6,10\},\{1,3,6\}\}$ $\{\{1,2,8\},\{2,8,10\},\{3,4,9\},\{3,9,10\},\{2,3,10\}\}$ $\{\{3,4,10\},\{2,3,10\},\{1,2,10\}\}$ $\{\{3,4,10\},\{2,3,6\},\{3,6,10\},\{1,2,10\},\{2,6,10\}\}$ $\{\{8,9,10\},\{2,3,8\},\{1,2,8\},\{3,4,9\},\{3,8,9\}\}$ $\{\{2,6,8\},\{1,2,8\},\{2,3,6\},\{3,4,9\},\{6,8,10\},\{3,9,10\},\{3,6,10\}\}$ $\{\{4,6,8\},\{4,7,8\},\{7,8,10\},\{2,4,6\},\{1,6,8\},\{1,2,6\}\}$ $\{\{6,7,8\},\{4,6,7\},\{7,8,10\},\{2,4,6\},\{2,6,8\},\{1,2,8\}\}$ $\{\{4,6,8\},\{2,4,6\},\{4,8,10\},\{2,6,8\},\{1,2,8\}\}$ $\{\{8,9,10\},\{7,8,9\},\{4,6,8\},\{4,7,8\},\{2,4,6\},\{2,6,8\},\{1,2,8\}\}$ $\{\{1,2,5\},\{4,6,8\},\{4,7,8\},\{7,8,10\},\{2,4,6\},\{2,5,8\},\{2,6,8\}\}$ $\{\{4,6,8\},\{3,4,6\},\{4,8,10\},\{2,6,8\},\{1,2,8\},\{2,3,6\}\}$ $\{\{2,4,6\},\{2,6,8\},\{1,2,8\},\{6,8,10\},\{4,6,10\}\}$ $\{\{8,9,10\},\{4,6,8\},\{2,4,6\},\{4,8,9\},\{2,6,8\},\{1,2,8\}\}$ $\{\{4,6,8\},\{2,4,6\},\{4,8,10\},\{1,6,8\},\{1,2,6\}\}$ $\{\{8,9,10\},\{1,2,5\},\{7,8,9\},\{4,6,8\},\{4,7,8\},\{2,4,6\},\{2,5,8\}, \{2,6,8\}\}$ $\{\{1,2,5\},\{6,7,8\},\{4,6,7\},\{7,8,10\},\{2,4,6\},\{2,5,8\},\{2,6,8\}\}$ $\{\{1,2,5\},\{5,6,8\},\{4,6,8\},\{4,7,8\},\{7,8,10\},\{2,5,6\},\{2,4,6\}\}$ $\{\{8,9,10\},\{1,2,5\},\{7,8,9\},\{6,7,8\},\{4,6,7\},\{2,4,6\},\{2,5,8\}, \{2,6,8\}\}$ $\{\{1,2,5\},\{6,7,8\},\{4,6,7\},\{7,8,10\},\{3,4,6\},\{2,5,8\},\{2,6,8\}, \{2,3,6\}\}$ $\{\{1,2,5\},\{4,6,7\},\{2,4,6\},\{2,5,8\},\{2,6,8\},\{6,8,10\},\{6,7,10\}\}$ $\{\{8,9,10\},\{1,2,5\},\{7,8,9\},\{4,6,8\},\{4,7,8\},\{3,4,6\},\{2,5,8\}, \{2,6,8\},\{2,3,6\}\}$ $\{\{8,9,10\},\{1,2,5\},\{7,8,9\},\{6,7,8\},\{4,6,7\},\{3,4,6\},\{2,5,8\}, \{2,6,8\},\{2,3,6\}\}$ $\{\{8,9,10\},\{7,8,9\},\{4,6,8\},\{4,7,8\},\{3,4,6\},\{2,6,8\},\{1,2,8\}, \{2,3,6\}\}$ $\{\{8,9,10\},\{7,8,9\},\{6,7,8\},\{4,6,7\},\{3,4,6\},\{2,6,8\},\{1,2,8\}, \{2,3,6\}\}$ $\{\{8,9,10\},\{7,8,9\},\{4,6,8\},\{4,7,8\},\{3,4,6\},\{2,3,6\},\{1,6,8\}, \{1,2,6\}\}$ $\{\{8,9,10\},\{4,6,8\},\{3,4,6\},\{4,8,9\},\{2,6,8\},\{1,2,8\},\{2,3,6\}\}$ $\{\{8,9,10\},\{7,8,9\},\{4,6,8\},\{4,7,8\},\{3,4,6\},\{1,6,8\},\{1,3,6\}\}$ $\{\{8,9,10\},\{7,8,9\},\{6,7,8\},\{4,6,7\},\{3,4,6\},\{2,3,6\},\{1,6,8\}, \{1,2,6\}\}$ $\{\{8,9,10\},\{7,8,9\},\{4,6,8\},\{4,7,8\},\{2,4,6\},\{1,6,8\},\{1,2,6\}\}$ $\{\{8,9,10\},\{5,6,8\},\{7,8,9\},\{4,6,8\},\{4,7,8\},\{3,4,6\},\{1,5,6\}, \{2,3,6\},\{1,2,6\}\}$ $\{\{8,9,10\},\{4,6,8\},\{3,4,6\},\{4,8,9\},\{2,3,6\},\{1,6,8\},\{1,2,6\}\}$ $\{\{4,6,8\},\{4,7,8\},\{7,8,10\},\{3,4,6\},\{2,3,6\},\{1,6,8\},\{1,2,6\}\}$ $\{\{4,6,8\},\{4,7,8\},\{7,8,10\},\{3,4,6\},\{1,6,8\},\{1,3,6\}\}$ $\{\{8,9,10\},\{7,8,9\},\{6,7,8\},\{4,6,7\},\{3,4,6\},\{1,6,8\},\{1,3,6\}\}$ $\{\{8,9,10\},\{5,6,8\},\{7,8,9\},\{4,6,8\},\{4,7,8\},\{3,4,6\},\{1,5,6\}, \{1,3,6\}\}$ $\{\{8,9,10\},\{7,8,9\},\{4,6,8\},\{4,7,8\},\{1,4,6\},\{1,6,8\}\}$ $\{\{8,9,10\},\{7,8,9\},\{4,7,8\},\{3,4,8\},\{1,3,8\}\}$ $\{\{8,9,10\},\{4,6,8\},\{3,4,6\},\{4,8,9\},\{1,6,8\},\{1,3,6\}\}$ $\{\{8,9,10\},\{4,6,8\},\{4,8,9\},\{1,4,6\},\{1,6,8\}\}$ $\{\{4,6,8\},\{4,7,8\},\{7,8,10\},\{1,4,6\},\{1,6,8\}\}$ $\{\{8,9,10\},\{7,8,9\},\{6,7,8\},\{4,6,7\},\{1,4,6\},\{1,6,8\}\}$ $\{\{8,9,10\},\{6,8,9\},\{1,4,6\},\{1,6,8\},\{4,6,9\}\}$ $\{\{8,9,10\},\{5,6,8\},\{4,6,8\},\{4,8,9\},\{1,5,6\},\{1,4,6\}\}$ $\{\{8,9,10\},\{4,8,9\},\{1,4,8\}\}$ $\{\{4,6,8\},\{1,4,6\},\{4,8,10\},\{1,6,8\}\}$ $\{\{8,9,10\},\{4,6,8\},\{2,4,6\},\{4,8,9\},\{1,6,8\},\{1,2,6\}\}$ $\{\{8,9,10\},\{4,6,7\},\{6,8,9\},\{6,7,9\},\{3,4,6\},\{1,6,8\},\{1,3,6\}\}$ $\{\{6,7,8\},\{4,6,7\},\{7,8,10\},\{3,4,6\},\{1,6,8\},\{1,3,6\}\}$ $\{\{8,9,10\},\{7,8,9\},\{6,7,8\},\{3,4,7\},\{3,6,7\},\{1,6,8\},\{1,3,6\}\}$ $\{\{8,9,10\},\{5,6,8\},\{7,8,9\},\{6,7,8\},\{4,6,7\},\{3,4,6\},\{1,5,6\}, \{1,3,6\}\}$ $\{\{6,7,8\},\{4,6,7\},\{7,8,10\},\{3,4,6\},\{2,3,6\},\{1,6,8\},\{1,2,6\}\}$ $\{\{6,7,8\},\{7,8,10\},\{3,4,7\},\{3,6,7\},\{1,6,8\},\{1,3,6\}\}$ $\{\{4,6,7\},\{3,4,6\},\{6,8,10\},\{6,7,10\},\{1,6,8\},\{1,3,6\}\}$ $\{\{5,6,8\},\{6,7,8\},\{4,6,7\},\{7,8,10\},\{3,4,6\},\{1,5,6\},\{1,3,6\}\}$ $\{\{5,6,8\},\{6,7,8\},\{4,6,7\},\{7,8,10\},\{3,4,6\},\{1,5,6\},\{2,3,6\}, \{1,2,6\}\}$ $\{\{5,6,8\},\{4,6,8\},\{4,7,8\},\{7,8,10\},\{3,4,6\},\{1,5,6\},\{1,3,6\}\}$ $\{\{5,6,8\},\{6,7,8\},\{7,8,10\},\{1,5,6\},\{3,4,7\},\{3,6,7\},\{1,3,6\}\}$ $\{\{5,6,8\},\{6,7,8\},\{4,6,7\},\{7,8,10\},\{1,5,6\},\{1,4,6\}\}$ $\{\{5,6,8\},\{6,7,8\},\{4,6,7\},\{7,8,10\},\{3,4,6\},\{3,5,6\},\{1,3,5\}\}$ $\{\{5,6,8\},\{4,6,7\},\{3,4,6\},\{1,5,6\},\{6,8,10\},\{6,7,10\},\{1,3,6\}\}$ $\{\{8,9,10\},\{2,3,8\},\{1,2,8\},\{3,8,9\},\{3,4,7\},\{3,7,9\}\}$ $\{\{8,9,10\},\{1,2,5\},\{7,8,9\},\{2,5,8\},\{2,3,8\},\{3,4,7\},\{3,7,8\}\}$ $\{\{6,7,9\},\{2,6,8\},\{1,2,8\},\{2,3,6\},\{3,4,7\},\{3,6,7\},\{6,8,10\}, \{6,9,10\}\}$ $\{\{2,3,6\},\{3,4,7\},\{3,6,7\},\{6,8,10\},\{6,7,10\},\{1,6,8\},\{1,2,6\}\}$ $\{\{4,6,7\},\{3,4,6\},\{2,6,8\},\{1,2,8\},\{2,3,6\},\{6,8,10\},\{6,7,10\}\}$ $\{\{1,2,5\},\{4,6,7\},\{3,4,6\},\{2,5,8\},\{2,6,8\},\{2,3,6\},\{6,8,10\}, \{6,7,10\}\}$ $\{\{4,6,7\},\{3,4,6\},\{1,2,8\},\{2,8,10\},\{2,3,6\},\{6,7,10\},\{2,6,10\}\}$ $\{\{4,6,7\},\{3,4,6\},\{2,3,6\},\{6,8,10\},\{6,7,10\},\{1,6,8\},\{1,2,6\}\}$ $\{\{4,6,7\},\{2,4,6\},\{2,6,8\},\{1,2,8\},\{6,8,10\},\{6,7,10\}\}$ $\{\{4,6,7\},\{2,4,6\},\{6,8,10\},\{6,7,10\},\{1,6,8\},\{1,2,6\}\}$ $\{\{4,6,7\},\{3,4,6\},\{2,3,6\},\{6,7,10\},\{1,2,6\},\{1,6,10\}\}$ $\{\{3,4,6\},\{2,3,6\},\{6,8,10\},\{1,6,8\},\{1,2,6\},\{4,6,10\}\}$ $\{\{4,6,7\},\{6,7,9\},\{3,4,6\},\{2,3,6\},\{6,8,10\},\{1,6,8\},\{1,2,6\}, \{6,9,10\}\}$ $\{\{8,9,10\},\{1,2,5\},\{2,5,8\},\{2,3,8\},\{3,8,9\},\{3,4,7\},\{3,7,9\}\}$ $\{\{8,9,10\},\{6,8,9\},\{2,6,8\},\{1,2,8\},\{2,3,6\},\{3,4,7\},\{3,7,9\}, \{3,6,9\}\}$ $\{\{8,9,10\},\{7,8,9\},\{6,7,8\},\{2,3,6\},\{3,4,7\},\{3,6,7\},\{1,6,8\}, \{1,2,6\}\}$ $\{\{8,9,10\},\{5,6,8\},\{7,8,9\},\{6,7,8\},\{4,6,7\},\{3,4,6\},\{1,5,6\}, \{2,3,6\},\{1,2,6\}\}$ $\{\{8,9,10\},\{4,6,7\},\{6,8,9\},\{6,7,9\},\{3,4,6\},\{2,3,6\},\{1,6,8\}, \{1,2,6\}\}$ $\{\{8,9,10\},\{6,8,9\},\{3,4,6\},\{2,3,6\},\{1,6,8\},\{1,2,6\},\{4,6,9\}\}$ $\{\{8,9,10\},\{4,6,7\},\{6,8,9\},\{6,7,9\},\{3,4,6\},\{2,6,8\},\{1,2,8\}, \{2,3,6\}\}$ $\{\{8,9,10\},\{4,6,7\},\{6,7,9\},\{3,4,6\},\{2,3,6\},\{1,2,6\},\{1,6,9\}, \{1,8,9\}\}$ $\{\{8,9,10\},\{6,8,9\},\{6,7,9\},\{2,3,6\},\{3,4,7\},\{3,6,7\},\{1,6,8\}, \{1,2,6\}\}$ $\{\{8,9,10\},\{5,6,8\},\{4,6,7\},\{6,8,9\},\{6,7,9\},\{3,4,6\},\{1,5,6\}, \{2,3,6\},\{1,2,6\}\}$ $\{\{8,9,10\},\{5,6,8\},\{4,6,7\},\{6,8,9\},\{6,7,9\},\{2,4,6\},\{1,5,6\}, \{1,2,6\}\}$ $\{\{8,9,10\},\{5,6,8\},\{6,8,9\},\{6,7,9\},\{1,5,6\},\{2,3,6\},\{3,4,7\}, \{3,6,7\},\{1,2,6\}\}$ $\{\{5,6,8\},\{4,6,7\},\{6,7,9\},\{3,4,6\},\{1,5,6\},\{2,3,6\},\{6,8,10\}, \{1,2,6\},\{6,9,10\}\}$ $\{\{8,9,10\},\{6,8,9\},\{6,7,9\},\{3,4,7\},\{3,6,7\},\{1,6,8\},\{1,3,6\}\}$ $\{\{8,9,10\},\{6,8,9\},\{6,7,9\},\{2,6,8\},\{1,2,8\},\{2,3,6\},\{3,4,7\}, \{3,6,7\}\}$ $\{\{8,9,10\},\{6,8,9\},\{2,3,6\},\{3,4,7\},\{1,6,8\},\{1,2,6\},\{3,7,9\}, \{3,6,9\}\}$ $\{\{8,9,10\},\{4,6,7\},\{6,7,9\},\{2,4,6\},\{1,2,6\},\{1,6,9\},\{1,8,9\}\}$ $\{\{8,9,10\},\{4,6,7\},\{6,7,9\},\{3,4,6\},\{1,3,6\},\{1,6,9\},\{1,8,9\}\}$ $\{\{4,6,7\},\{6,7,9\},\{3,4,6\},\{2,3,6\},\{1,2,6\},\{1,6,9\},\{1,9,10\}\}$ $\{\{4,6,7\},\{6,7,9\},\{2,4,6\},\{1,2,6\},\{1,6,9\},\{1,9,10\}\}$ $\{\{8,9,10\},\{5,6,8\},\{7,8,9\},\{6,7,8\},\{1,5,6\},\{2,3,6\},\{3,4,7\}, \{3,6,7\},\{1,2,6\}\}$ $\{\{8,9,10\},\{1,2,5\},\{5,6,8\},\{7,8,9\},\{6,7,8\},\{4,6,7\},\{3,4,6\}, \{2,5,6\},\{2,3,6\}\}$ $\{\{8,9,10\},\{1,2,5\},\{5,6,8\},\{7,8,9\},\{6,7,8\},\{2,5,6\},\{2,3,6\}, \{3,4,7\},\{3,6,7\}\}$ $\{\{8,9,10\},\{1,2,5\},\{7,8,9\},\{6,7,8\},\{2,5,8\},\{2,6,8\},\{2,3,6\}, \{3,4,7\},\{3,6,7\}\}$ $\{\{8,9,10\},\{1,2,5\},\{5,6,8\},\{6,8,9\},\{6,7,9\},\{2,5,6\},\{2,3,6\}, \{3,4,7\},\{3,6,7\}\}$ $\{\{8,9,10\},\{1,2,5\},\{2,3,5\},\{5,6,8\},\{7,8,9\},\{6,7,8\},\{3,5,6\}, \{3,4,7\},\{3,6,7\}\}$ $\{\{8,9,10\},\{7,8,9\},\{6,7,8\},\{4,6,7\},\{2,4,6\},\{2,6,8\},\{1,2,8\}\}$ $\{\{1,2,5\},\{6,7,8\},\{7,8,10\},\{2,5,8\},\{2,6,8\},\{3,4,7\},\{2,6,7\}, \{2,3,7\}\}$ $\{\{8,9,10\},\{6,7,9\},\{3,4,7\},\{3,6,7\},\{1,3,6\},\{1,6,9\},\{1,8,9\}\}$ $\{\{6,7,9\},\{3,4,7\},\{3,6,7\},\{1,3,6\},\{1,6,9\},\{1,9,10\}\}$ $\{\{3,4,7\},\{3,6,7\},\{6,8,10\},\{6,7,10\},\{1,6,8\},\{1,3,6\}\}$ $\{\{1,4,10\}\}$ $\{\{8,9,10\},\{3,4,5\},\{5,6,8\},\{4,5,6\},\{4,6,7\},\{6,8,9\},\{6,7,9\}, \{1,3,5\}\}$ $\{\{4,6,7\},\{6,7,9\},\{3,4,6\},\{2,3,6\},\{1,2,6\},\{1,6,10\},\{6,9,10\}\}$ $\{\{4,6,7\},\{6,7,9\},\{3,4,6\},\{6,8,10\},\{1,6,8\},\{1,3,6\},\{6,9,10\}\}$ $\{\{5,6,8\},\{4,6,8\},\{4,7,8\},\{7,8,10\},\{1,5,6\},\{1,4,6\}\}$ $\{\{1,4,6\},\{6,8,10\},\{1,6,8\},\{4,6,10\}\}$ $\{\{5,6,8\},\{4,6,8\},\{1,5,6\},\{1,4,6\},\{4,8,10\}\}$ $\{\{1,4,6\},\{4,6,10\},\{1,6,10\}\}$ $\{\{5,6,8\},\{1,5,6\},\{1,4,6\},\{6,8,10\},\{4,6,10\}\}$ $\{\{3,4,6\},\{6,8,10\},\{1,6,8\},\{1,3,6\},\{4,6,10\}\}$ $\{\{1,4,6\},\{6,8,10\},\{1,6,8\},\{4,6,9\},\{6,9,10\}\}$ $\{\{2,4,6\},\{6,8,10\},\{1,6,8\},\{1,2,6\},\{4,6,10\}\}$ $\{\{5,6,8\},\{4,6,8\},\{2,4,6\},\{1,5,6\},\{4,8,10\},\{1,2,6\}\}$ $\{\{4,6,8\},\{3,4,6\},\{4,8,10\},\{2,3,6\},\{1,6,8\},\{1,2,6\}\}$ $\{\{2,3,6\},\{3,4,7\},\{3,6,7\},\{6,7,10\},\{1,2,6\},\{1,6,10\}\}$ $\{\{5,6,8\},\{6,7,8\},\{7,8,10\},\{3,5,6\},\{1,3,5\},\{3,4,7\},\{3,6,7\}\}$ $\{\{8,9,10\},\{5,6,8\},\{4,6,7\},\{6,8,9\},\{6,7,9\},\{1,5,6\},\{1,4,6\}\}$ $\{\{1,2,5\},\{2,3,5\},\{5,6,8\},\{6,7,8\},\{4,6,7\},\{7,8,10\},\{3,4,6\}, \{3,5,6\}\}$ $\{\{8,9,10\},\{5,6,8\},\{4,5,6\},\{4,6,7\},\{6,8,9\},\{6,7,9\},\{1,4,5\}\}$ $\{\{5,6,8\},\{4,6,8\},\{4,7,8\},\{7,8,10\},\{3,4,6\},\{1,5,6\},\{2,3,6\}, \{1,2,6\}\}$ $\{\{8,9,10\},\{4,6,7\},\{6,7,9\},\{3,4,6\},\{1,3,6\},\{1,6,9\},\{5,8,9\}, \{1,5,9\}\}$ $\{\{8,9,10\},\{5,6,8\},\{7,8,9\},\{6,7,8\},\{4,6,7\},\{1,5,6\},\{1,4,6\}\}$ $\{\{8,9,10\},\{1,2,5\},\{7,8,9\},\{2,5,8\},\{3,4,7\},\{2,7,8\},\{2,3,7\}\}$ $\{\{8,9,10\},\{1,2,5\},\{7,8,9\},\{6,7,8\},\{2,5,8\},\{2,6,8\},\{3,4,7\}, \{2,6,7\},\{2,3,7\}\}$ } \begin{thebibliography}{9} \bibitem{Fuku}{\bf D. Avis and K. Fukuda} {\em A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of Arrangements and Polyhedra},Discrete and Comp. Geom. Vol 8,(1992),295-313. \bibitem{mac}{\bf D. Bayer,M. Stillman and M. Stillman} {\em Macaulay User Manual.} Cornell University,1989. \bibitem{BIFIST}{\bf L. Billera,P. Filliman and B. Sturmfels} {\em Constructions and Complexity of Secondary Polytopes}. Adv. in Math. 83 ,1990,155-179. \bibitem{BiGelSt}{\bf L. Billera,I.M. Gelfand and B. Sturmfels} {\em Duality and Minors of Secondary Polyhedra}. J. of Comb.Theory B. Vol. 57,2,1993,258-268. \bibitem{OMB}{\bf A. Bj\"orner,M. Las Vergnas,B. Sturmfels,N. White,G. Ziegler} {\em Oriented Matroids} Cambridge University Press,Cambridge 1992. \bibitem{Brylas}{\bf T. Brylawski } { \em Constructions} ``Theory of Matroids'',(Ed. N.White) Cambridge University Press,Cambridge (1986). \bibitem{Edels}{\bf H. Edelsbrunner}{\em Algorithms in Combinatorial Geometry}, Springer, New York, 1987. \bibitem{GKZ} {\bf I.M. Gel'fand,M.M. Kapranov and A.V. Zelevinsky} {\em Discriminants of Polynomials in Several Variables and Triangulations of Newton Polytopes},Algebra i analiz 2,1990,1-62. (English translation in {\em Leningrad Math. J. 2,1991,449-505). \bibitem{GKZbook} {\bf I.M. Gel'fand,M.M. Kapranov and A.V. Zelevinsky} {\em Discriminants and Resultants} Birkh\"auser, Boston, 1993. \bibitem{oneGKZ} {\bf I.M. Gel'fand,M.M. Kapranov and A.V. Zelevinsky} {\em Newton polyhedra of principal A-determinants} Doklady Akad. Nauk SSSR. \bibitem{GrLoSc}{\bf M. Gr\"otschel, L. Lov\'asz and A. Schrijver} {\em Geometric Algorithms and Combinatorial Optimization},Springer, Berlin, Heidelberg, 1988. \bibitem{duke}{\bf M.M. Kapranov,B. Sturmfels and A.V. Zelevinsky} {\em Chow Polytopes and General Resultants}, Duke Math. Journal,Vol 67,1992,189-218. \bibitem{Lee}{\bf C.W. Lee} {\em Regular Triangulations of Convex Polytopes}. Applied Geometry and Discrete Mathematics-The Victor Klee Festschrift. (P. Gritzmann and B. Sturmfels eds.) Dimacs Series in Discrete Math. and Theoretical Comp. Science,Vol 4,1991,443-456. \bibitem{Masa}{\bf T. Masada} {\em An Output Size sensitive Algorithm for the Enumeration of Regular Triangulations}, University of Tokio, manuscript, 1993. \bibitem{Bernd1}{\bf B. Sturmfels} {\em Gr\"obner Bases of Toric Varieties}, T\^ohoku Math. J.,1991,Vol 43,No. 2,249-251. \bibitem{Bernd2}{\bf B. Sturmfels} {\em Asymptotic Analysis of Toric Ideals}, Memoirs of the Faculty of Science,Kyushu University Ser.A,Vol. 46,1992,217-228. \bibitem{Todd}{\bf M.J. Todd}{\em The Computation of Fixed Points and Applications}, Springer-Verlag, Berlin, 1976. \bibitem{ToddLev}{\bf M.J. Todd and L. Tuncel} {\em A new Triangulation for Simplicial Algorithms}, SIAM J. Discrete Math.,Vol 6, 1,,167-180. \end{thebibliography} \vskip 2cm \noindent Jes\'us A. de Loera. Center for Applied Mathematics,Cornell University,Ithaca,NY 14583,\quad {\em jdl@cam.cornell.edu} \end{document}