|
Vestnik Volgogradskogo gosudarstvennogo universiteta. Seriya 1. Mathematica. Physica, 2014, Issue 5(24), Pages 40–45
(Mi vvgum21)
|
|
|
|
This article is cited in 1 scientific paper (total 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.
Citation:
V. V. Popov, “On algorithm of numbering of triangulations”, Vestnik Volgogradskogo gosudarstvennogo universiteta. Seriya 1. Mathematica. Physica, 2014, no. 5(24), 40–45
Linking options:
https://www.mathnet.ru/eng/vvgum21 https://www.mathnet.ru/eng/vvgum/y2014/i5/p40
|
Statistics & downloads: |
Abstract page: | 102 | Full-text PDF : | 108 | References: | 38 |
|