We propose two algorithms to enumerate triangulations. These
algorithms enumerate all triangulations, regular or not, for arbitrary
configurations of points in any dimensions. Our first algorithm
characterizes triangulations as maximal independent sets of the
intersection graph. This graph has the maximal dimensional simplices
of the given point configuration as vertices, and edges between two
simplices whose intersection is not a face for at least one of them.
We enumerate the maximal independent sets of this graph, which form a
superset of triangulations. The algorithm runs in time proportional to
the size of this superset and requires memory only of the size of a
triangulation. Our second algorithm enumerates the independent sets
of the intersection graph whose interior is connected. These sets also
form a superset of triangulations. This algorithm runs in time
proportional to the size of this superset and requires memory twice
the size of a triangulation.
We are also interested in the triangulations of products of two
simplices. Since the polytope of this product is symmetric, it is
important to enumerate the classes of triangulations in respect of
this symmetry. We modify our second algorithm to enumerate the
classes of independent sets with connected interior, which forms a
superset of the classes of triangulations. This modification also
runs in time proportional to the size of this superset and requires
memory twice the size of a triangulation.