We propose algorithms to enumerate (1) classes of regular
triangulations in respect of symmetry for products of two simplices
and (2) all triangulations, regular or not, for arbitrary
configurations of points. There are many results for triangulations
in two dimension, but little is known for higher dimensions. Both
objects we enumerate in this paper are for general dimensions.
Products of two simplices, our first object, are polytopes rather
simple, but their triangulations are not yet well understood. Since
these polytopes are highly symmetric, counting all triangulations
naively is inefficient: we may count the ``same'' triangulation many
times. Our first algorithm enumerates the classes of regular
triangulations, a subset of triangulations, with respect to the
symmetry. We use reverse search technique, utilizing the symmetric
structure of the polytope. This enables time complexity linear to the
number of these classes, and space complexity of the size of several
triangulations.
Even for the polytope of this product, a nonregular triangulation was
found. Though algorithms to enumerate regular triangulations are
studied well, no efficient algorithm to enumerate all triangulations,
including nonregular ones, has been known. Our second algorithm
handles this problem for arbitrary configurations of points. It
formulates triangulations as maximal independent sets of the
intersection graph, and applies a general maximal independent set
enumeration algorithm. The intersection graph here is the graph with
all maximal dimensional simplices the vertices and edges between those
intersecting improperly. This algorithm works in time proportional to
the number of maximal independent sets. We last apply this second
algorithm to the polytope of the product.