Popov V.V. On algorithm of numbering of triangulations
- Details
- Hits: 904
Popov Vladimir Valеntinovich
Candidate of Physical and Mathematical Sciences, Associate Professor, Department of Computer Sciences and Experimental Mathematics, Volgograd State University
This email address is being protected from spambots. You need JavaScript enabled to view it. , This email address is being protected from spambots. You need JavaScript enabled to view it. , This email address is being protected from spambots. You need JavaScript enabled to view it.
Prosp. Universitetsky, 100, 400062 Volgograd, Russian Federation
This email address is being protected from spambots. You need JavaScript enabled to view it. , This email address is being protected from spambots. You need JavaScript enabled to view it. , This email address is being protected from spambots. You need JavaScript enabled to view it.
Prosp. Universitetsky, 100, 400062 Volgograd, Russian Federation
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 = {p1,p2,...,pN} is a finite set of points in three-dimensional space.
The triangulation of this set is such a sequence S1, S2, ..., Sk of tetrahedrons with vertexs from P, which union is equal to convex hull conv(P) of P, and the intersection Si∩ Sj, i≠ j is or empty, or is the common vertex or the common edge or the common face of tetrahedrons Si and Sj, and each point pi is the vertex of some Sj.
At first, the algorithm A is described, which gives us the list of all triangulations on P, containing some tetrahedron S1 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 S1, S2, ..., Sk which can be completed to some triangulations for P, but the union V = S1∪ S2∪ ... ∪ of Sk is not equal to 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 ∩ S = F. Among tetrahedrons S, which can be
constructed by this way, we choise such S, that the sequence (i1,i2,i3,i4) of numbers of his vertex has a minimum value with respect to lexicographic order.
Now we put Sk+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 conv(P). We assume that G∩P={p1,p2,...,pl}, where l≥3. and segment [p1,p2] doesn’t contains some points from P other than p1and p2. Let 2 < i3≤ l < i4 and S is the tetrahedrons with vertexes p1, p2,pi3,pi4, which does not containes the points from P other than his vertexs. Applying algorithm A to S, we obtain some triangulations of a set P.
Changing i3, i4, we get all the triangulations. By this way we realies algorithm A.
Algorithms A and 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 ∪{p}, where p is the point of the edge of cube. Then P′ has 276 triangulations.
Let P = {p1,p2,...,pN} is a finite set of points in three-dimensional space.
The triangulation of this set is such a sequence S1, S2, ..., Sk of tetrahedrons with vertexs from P, which union is equal to convex hull conv(P) of P, and the intersection Si∩ Sj, i≠ j is or empty, or is the common vertex or the common edge or the common face of tetrahedrons Si and Sj, and each point pi is the vertex of some Sj.
At first, the algorithm A is described, which gives us the list of all triangulations on P, containing some tetrahedron S1 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 S1, S2, ..., Sk which can be completed to some triangulations for P, but the union V = S1∪ S2∪ ... ∪ of Sk is not equal to 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 ∩ S = F. Among tetrahedrons S, which can be
constructed by this way, we choise such S, that the sequence (i1,i2,i3,i4) of numbers of his vertex has a minimum value with respect to lexicographic order.
Now we put Sk+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 conv(P). We assume that G∩P={p1,p2,...,pl}, where l≥3. and segment [p1,p2] doesn’t contains some points from P other than p1and p2. Let 2 < i3≤ l < i4 and S is the tetrahedrons with vertexes p1, p2,pi3,pi4, which does not containes the points from P other than his vertexs. Applying algorithm A to S, we obtain some triangulations of a set P.
Changing i3, i4, we get all the triangulations. By this way we realies algorithm A.
Algorithms A and 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 ∪{p}, where p is the point of the edge of cube. Then P′ has 276 triangulations.
Key words: triangulation, tetrahedron, simplex, number of triangulations, convex hull.
On Algorithm of Numbering of Triangulations by Popov V.V. is licensed under a Creative Commons Attribution 4.0 International License.
Citation in English: Science Journal of Volgograd State University. Mathematics. Physics. №5 (24) 2014 pp. 40-45
 8_Popov_V.V..pdfURL: https://mp.jvolsu.com/index.php/en/component/attachments/download/333 | 859 Downloads |