This article is cited in
1 paper
Mathematics
On algorithm of numbering of triangulations
V. V. Popov Volgograd State University
Abstract:
In [1] the algorithm of numbering of all triangulations of
a finite set on the plane is offered.
This paper describes the modification
of this algoritm for subset of points in three-dimensional space.
Let
$P =\{ p_1, p_2, \ldots, p_N\} $ is a finite
set of points in three-dimensional space.
The triangulation of this set is such a sequence
$S_1$,
$S_2$,
$\ldots$,
$S_k$ of
tetrahedrons with vertexs from
$P$,
which union is equal to
convex hull
${\rm conv } (P)$ of
$P$, and
the intersection
$S_i\cap S_j$,
$i\neq j$ is or empty,
or is the common vertex or the common edge or the common face
of tetrahedrons
$S_i$ and
$S_j$, and each point
$p_i$
is the vertex of some
$S_j$.
At first, the algorithm
${\mathcal A } $ is described,
which gives us the list of all
triangulations on
$P$, containing some tetrahedron
$S_1$ with vertexs from a set of
$P$ without points
from
$P$ other than his vertexs.
Let at some
$k$ the list of tetrahedrons be already defined
$S_1$,
$S_2$,
$\ldots$,
$S_k$ which can be completed to some
triangulations for
$P$, but the union
$V=S_1\cup S_2\cup \ldots \cup of S_k$
is not equal to
${\rm conv (P)}$.
Then there will be such two-dimensional face
$F$ a set
$V$ and such tetrahedron of
$S$ with vertexs from
$P$ which doesn't contain
points of a set
$P$ other than his vertexs, and
$V\cap S=F$.
Among tetrahedrons
$S$, which can be constructed by this way,
we choise such
$S$, that the sequence
$(i_1, i_2, i_3, i_4)$ of numbers
of his vertex has a minimum value with respect to lexicographic order.
Now we put
$S_{k+1}=S$. After some such a steps we get a triangulation
of
$P$.
To build other triangulations it is necessary to delete tetrahedrons with big
numbers and add new tetrahedrons before receiving new triangulations.
Let
$G$ be a boundary of the set
${\rm conv}(P)$. We assume that
$G\cap P=\{p_1,p_2,\ldots,p_l\}$, where
$l\geq 3$
and segment
$[p_1, p_2]$ doesn't contains some points from
$P$ other than
$p_1$ and
$p_2$.
Let
$2<i_3\leq l<i_4$ and
$S$ is the
tetrahedrons with vertexes
$p_1$,
$p_2$,
$p_{i_3}$,
$p_{i_4}$,
which does not containes the points
from
$P$ other than his vertexs.
Applying algorithm
${\mathcal A } $ to
$S$, we obtain some
triangulations of a set
$P$. Changing
$i_3$,
$i_4$, we
get all the triangulations.
By this way we realies algorithm
${\mathcal A } $.
Algorithms
${\mathcal A } $ and
${\mathcal B }$ allows us to receive, for example,
the following results:
(1) Let
$P$ is the set of vertexs of a cube.
Then the number of triangulations of
$P$ is equall
$74$.
(2) Let
$P'=P\cup\{p\}$, where
$p$ is the point of the edge of cube.
Then
$P'$ has
$276$ triangulations.
Keywords:
triangulation, tetrahedron, simplex, number of triangulations, convex hull.
UDC:
517.518.85+517.27
BBK:
22.144