## Popov V.V. On algorithm of numbering of triangulations

- Details
- Hits: 429

*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 = {p

_{1},p

_{2},...,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}, ..., S

_{k}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 S

_{i}and S

_{j}, and each point pi is the vertex of some S

_{j}.

At first, the algorithm 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}, ..., S

_{k}which can be completed to some triangulations for P, but the union V = S

_{1}∪ S

_{2}∪ ... ∪ of S

_{k}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 (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 conv(P). We assume that G∩P={p

_{1},p

_{2},...,pl}, where l≥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}≤ l < i

_{4}and S is the tetrahedrons with vertexes p

_{1}, p

_{2},pi

_{3},pi

_{4}, 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 i

_{3}, i

_{4}, 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**