On the parallel algorithm of numbering of a

V. V. Popov

Matematičeskaâ fizika i kompʹûternoe modelirovanie, no. 5 (2016), pp. 85-96

Résumé

The task of constructing a triangulation of a finite subset of the plane considered by many authors (see, for example, [5–8]). In [1] it was offered the algorithm for constructing all the triangulations of a finite set on the plane. The corresponding algorithm for three-dimensional space described in [2]. In this paper we consider the following problem: Let $P$ is a (closed) polygon in the plane and $P = \{p_1, p_2, \ldots, p_N \}$ is a finite subset of ${{\mathbf R}}^2$, including all the vertices of the polygon $F$. It necessary to numbering all the triangulations of the polygon $F$ relative to a set $P$. In this paper we propose a parallel algorithm for solving this problem. Some of the results announced in [4]. The triangulation $T$ of a polygon $F$ relative to a set $P$ is a collection $S_1$, $S_2$, $\ldots$, $S_m$ of triangles, satisfying the following conditions: (1) Each point $p_i \in P$ is a vertex of at least one of the triangle $S_j$. (2) The vertices of any triangle $S_j$ lie in the set $P$. (3) If $i \neq j$, then the triangles $S_i$ and $S_j$ either have no common points, or have (only) a common vertex, or have (only) a common edge. (4) The union of triangles $S_1$, $S_2$, $\ldots$, $S_m$ coincides with the polygon $F$. Let $Tr(F, P)$ is the set of all triangulations, satisfying conditions (1)–(4). Thus, it necessary to list all the triangulation $T \in Tr(F,P)$. To describe the parallel algorithm for solving this problem we need to use the notion of septum. Let $l$ is such a straight lines in the plane, which intersect $F$ and disjoint with $P$. We call the septum defined by the triple $F$, $P$, $l$, a set $\Pi$ of triangles, which satisfies the following conditions: (a) All vertices of any triangle $S \in \Pi $ lies in the set $P$. (b) If $ S, S '\in \Pi $ and $S\neq S'$, then $S\cap S'=\emptyset$, or $S$ and $S'$ have (only) a common vertex or have (only) a common edge. (c) The union of all triangles $ S \in \Pi $ contains the set $ F \cap l $ and itself is contained in $F$. Let $T \in Tr(F,P)$ is a triangulation of the polygon $F$ relative to the set $P$ and $l$ is a straight lines, $l\cap F\neq\emptyset$ and $l\cap P = \emptyset$. Then $\Pi=\{S\in T: S\cap l\neq\emptyset\}$ is a septum defined by the triple $F$, $P$, $l$. The line $l$ divides the plane ${{\mathbf R}}^2$ into two half-planes $H_1$ and $H_2$. Let, for $i = 1, 2$, $ T_i $ is the set of all triangles $S \in T$, that lies in $H_i$, and let $F_i$ is the union of triangles $S \in T_i$. Then $T_i$ is a triangulation of polygon $F_i$ relative to the set $P \cap F_i$. Thus, if we are given a triangulation $ T \in Tr(F, P) $, it is possible to uniquely identify the septum $ \Pi $ and the triangulations $ T_1$, $T_2$. On the contrary, if we have $ \Pi $, $ T_1$ and $T_2$, then the family of all triangles from $\Pi$, $ T_1$ and $T_2$ gives us triangulation $T$. In this way, we can list all the triangulation $ T \in Tr(F,P)$: we need only to renumber all the the septa $ \Pi $, defined by the triple $F$, $P$, $l$, and for each such $\Pi$ to renumber the triangulations $T_1 \in Tr(F_1,P\cap F_1)$ and $T_2 \in Tr(F_2,P\cap F_2)$. We now present some of the results obtained by the described methods. Example 1. Consider the set $L_{m,n}$ on the plane, consisting of $n\cdot m$ points: $$L_{m,n}=\{(i,j):i=1,2,\ldots,n,\ j=1,2,\ldots, m\},$$ where $ n, m \geq 1 $—integers. Let $ F $ is the convex hull of $ P = L_{m, n} $. Then the number of triangulations in $ Tr (F, P) $ for some $ n $ and $ m $ we calculated in three ways: 1) Using algorithm from [1] for constructing all triangulations $T\in Tr (F, P) $ (Algorithm 1). 2) Using algorithm we describe above, where $l$ is a horizontal line (Algorithm 2). 3) Using the modification of the algorithm from 2) in which we need horizontal line and vertical line (Algorithm 3). The table shows the operating time of the computer program (in seconds). Example 6. The following problem arises often: for given $F$ and $P$ we need to numbering only those triangulation $T\in Tr(F,P)$, that satisfy certain additional conditions (Filtering problem). The following table shows (for some $m$, $n$ and $L\in {{\mathbf R}}$) the number of such a triangulation $T$ from Example 1, that for any triangle $S\in T$ the length of the sides of $S$ does not exceed $L$.

Détail

Mots-clés : triangulation
Keywords: the number of triangulations, the tree of triangulations, memory volume estimate, Catalan number, convex hull.

Bibliographie

[1] V.\;A. Klyachin, V.\;V. Popov, “Chanes Method for Storage of Multidimensional Triangulation”, Science Journal of Volgograd State University. Mathematics. Physics, 2013, no. 2 (19), 71–79

[2] V.\;V. Popov, “On Algorithm of Numbering of Triangulations”, Science Journal of Volgograd State University. Mathematics. Physics, 2014, no. 5 (24), 40–45

[3] V.\;V. Popov, “On Algorithm of Numbering the Spanning Trees in a Connected Graph”, Science Journal of Volgograd State University. Mathematics. Physics, 2015, no. 2 (27), 6–16

[4] V.\;V. Popov, “On Parallel Algorithm of Numbering of the Triangulations of a Finite Subset of the Plane”, Geometricheskiy analiz i ego prilozheniya, Materialy III Mezhdunarodnoy shkolykonferentsii, Izd-vo VolGU, Volgograd, 2016, 168–170 | Zbl

[5] F. Preparata, M. Shamos, Computational Geometry: An Introduction, Mir Publ., M., 1989, 478 pp.

[6] A.\;V. Skvortsov, Delaunay Triangulation and Its Application, Izd-vo Tom. un-ta, Tomsk, 2002, 128 pp.

[7] O. Aichholzer, T. Hackl, B. Vogtenhuber, C. Huemer, F. Hurtado, H. Krasser, “On the Number of Plane Geometrical Graphs”, Graphs and Combinatorics, 23 (2007), 67–84 | DOI | MR | Zbl

[8] F. Hurtado, M. Noy, “Graph of triangulations of a convex polygon and tree of triangulations”, Computational Geometry, 13 (1999), 179–188 | DOI | MR | Zbl

[9] G. Polia, “On picture-writing”, The American Mathematical Monthly, 63 (1956), 689–697 | DOI | MR