Vestnik Volgogradskogo gosudarstvennogo universiteta. Seriya 1. Mathematica. Physica
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mathematical Physics and Computer Simulation:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
Full-text PDF (310 kB) Citations (1)
References:
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.
Document Type: Article
UDC: 517.518.85+517.27
BBC: 22.144
Language: Russian
Citation: V. V. Popov, “On algorithm of numbering of triangulations”, Vestnik Volgogradskogo gosudarstvennogo universiteta. Seriya 1. Mathematica. Physica, 2014, no. 5(24), 40–45
Citation in format AMSBIB
\Bibitem{Pop14}
\by V.~V.~Popov
\paper On algorithm of numbering of triangulations
\jour Vestnik Volgogradskogo gosudarstvennogo universiteta. Seriya 1. Mathematica. Physica
\yr 2014
\issue 5(24)
\pages 40--45
\mathnet{http://mi.mathnet.ru/vvgum21}
Linking options:
  • https://www.mathnet.ru/eng/vvgum21
  • https://www.mathnet.ru/eng/vvgum/y2014/i5/p40
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Mathematical Physics and Computer Simulation
    Statistics & downloads:
    Abstract page:102
    Full-text PDF :108
    References:38
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024