RUS  ENG
Full version
JOURNALS // Mathematical Physics and Computer Simulation // Archive

Vestnik Volgogradskogo gosudarstvennogo universiteta. Seriya 1. Mathematica. Physica, 2014 Issue 5(24), Pages 40–45 (Mi vvgum21)

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



© Steklov Math. Inst. of RAS, 2024