The aim of this research is to study triangulations in general
dimension through enumeration.
Many results have been achieved for triangulations in dimension two.
For triangulations in general dimension, regular triangulations,
which form a subclass of all
triangulation, have been studied recently.
However nonregular triangulations are not yet well understood
We first propose an algorithm to enumerate all triangulations for arbitrary
configurations of points.
Regular triangulations form a nice
algebraic structure, and algorithms to enumerate them efficiently is
known.
However, no such thing was known for all triangulations.
We accomplish this by characterizing triangulations as maximal
independents sets of an intersection graph, and enumerating the
maximal independent sets.
The intersection graph here, is a graph with vertices the maximal
dimensional simplices of the given point configuration, and edges
between improperly intersecting simplices. Thus triangulations form a
subset of the maximal independent sets of this graph.
We next propose an algorithm to enumerate efficiently the regular
triangulations of
highly symmetric polytopes. Among those we are interested in
triangulations of products of two simplices and hypercubes. It is not
efficient to enumerate naively the triangulations of these symmetric
polytopes, because we may count the ``same'' triangulation many times.
We accomplish this by enumerating classes of triangulations in respect
of symmetry.
This is done by introducing reverse search for classes of objects.
We also consider facets of independent set polytopes of intersection graphs
of simplices.
We deal with two intersection graphs.
The intersection graph of $d$-simplices and the graph of
$(d-1)$-simplices for
point configurations having dimension $d$.
The independent set polytopes are the convex hulls of
the incidence vectors of the independent sets of these graphs.
As a special case, we deal with points spanning the plane.
We give a proof that an inequality known to be powerful for
the minimum weight
triangulation problem is defining a facet of the independent set polytope.