Last Modified: 2000-08-22 (Minor Update on 2003-05-02)

# Triangulations

### What of triangulations are we interested in?

Given a point configuration, there are several triangulations of the
convex hull of the points, using only the given points. For example,
the point configuration made by the vertices of a pentagon has five
triangulations indicated in the figure.

Triangulations are not merely existing, but they have some structure.
In the example of the pentagon, pairs of triangulations which
can change to each other by changing one edge (such operations are
called flips) are connected by dotted lines. So, with respect to this
local transformation, the five triangulations are forming a
structure of a pentagonal graph.

The aim of our research is to study the structure of triangulations in
general dimension.

### Our results

(Publications)

- Enumeration of triangulations
- We have established algorithms to enumerate efficiently the
whole set of triangulations
for a given point set.
We also wrote programs implementing these algorithms.
Point configurations having triangulations of mathematical
interest often happen to be symmetric.
We also have devised an algorithm to enumerate regular
triangulations for such symmetric point configurations efficiently.
- Triangulations and dissections
- In a triangulation, the components forming the division
are required to be touching nicely.
However, for some applications such as volume computation,
only the decomposition is enough, and they need not be touching
nicely (such decompositions are called
dissections).
We have found examples showing the difference of these
two classes of decomposition:
an example with the minimal dissection using less simplices
than minimal
triangulation, maximal dissection using more simplices than
maximal triangulation, upper and lower bounds for the size of
dissections.
- Incremental construction properties of simplicial complexes
- Simplicial complexes are forming a superclass of triangulations.
Several kinds of incremental construction properties
of simplicial complexes have been known.
We have shown relations between some of these properties.
Study of such incremental construction properties are important
when handling geometric objects by computer.

### Applications of triangulations

Polytopes often become easier to handle when divided into smaller
parts. There are many areas requiring techniques to handle three
dimensional point configurations, and triangulations become
important there.
Examples of such areas are computer graphics,
simulations for engineering, and handling 3D structures of DNA or proteins in
biology.