On the parallel algorithm of numbering triangulations of the polygon in the plane

The task of constructing a triangulation of a finite subset of the plane is 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 is described in [2]. In this paper we consider the following problem: Let be a (closed) polygon in the plane and = {𝑝1, 𝑝2,..., 𝑝𝑁} is a finite subset of R2, including all the vertices of the polygon 𝐹. It is necessary to numbering all the triangulations of the polygon relative to a set 𝑃. In this paper we propose a parallel algorithm for solving this problem. Some of the results are announced in [4]. The triangulation of a polygon relative to a set is a collection ґ𝑆1, 𝑆2,..., of triangles, satisfying the following conditions: (1) Each point ∈ is a vertex of at least one of the triangle 𝑆𝑗. (2) The vertices of any triangle lie in the set 𝑃. (3) If 𝑖 ̸= 𝑗, then the triangles and either have no common points, or have (only) a common vertex, or have (only) a common edge. (4) The union of triangles 𝑆1, 𝑆2,..., coincides with the polygon 𝐹. Let 𝑇𝑟(𝐹, 𝑃) be the set of all triangulations, satisfying conditions (1)-(4). Thus, it is necessary to list all the triangulation ∈ 𝑇𝑟(𝐹, 𝑃). To describe the parallel algorithm for solving this problem we need to use the notion of septum. Let be such a straight lines in the plane, which intersect and disjoint with 𝑃. We call the septum defined by the triple 𝐹, 𝑃, 𝑙, a set Π of triangles, which satisfies the following conditions: (a) All vertices of any triangle ∈ Π lie in the set 𝑃. (b) If 𝑆, 𝑆′ ∈ Π and 𝑆 ̸= 𝑆′, then ∩ 𝑆′ = ∅, or and 𝑆′ have (only) a common vertex or have (only) a common edge. (c) The union of all triangles ∈ Π contains the set ∩ and itself is contained in 𝐹. Let ∈ 𝑇𝑟(𝐹, 𝑃) is a triangulation of the polygon relative to the set and is a straight line, ∩ 𝐹 ̸= ∅ and ∩ = ∅. Then Π = {𝑆 ∈ : ∩ 𝑙 ̸= ∅} is a septum defined by the triple 𝐹, 𝑃, 𝑙. The line divides the plane R2 into two half-planes 𝐻1 and 𝐻2. Let, for = 1, 2, be the set of all triangles ∈ 𝑇, that lies in 𝐻𝑖, and let be the union of triangles ∈ 𝑇𝑖. Then is a triangulation of polygon relative to the set ∩ 𝐹𝑖. Thus, if we are given a triangulation ∈ 𝑇𝑟(𝐹, 𝑃), it is possible to uniquely identify the septum Π and the triangulations 𝑇1, 𝑇2. On the contrary, if we have Π, 𝑇1 and 𝑇2, then the family of all triangles from Π, 𝑇1 and 𝑇2 gives us triangulation 𝑇. In this way, we can list all the triangulation ∈ 𝑇𝑟(𝐹, 𝑃): we need only to renumber all the the septa Π, defined by the triple 𝐹, 𝑃, 𝑙, and for each such Π to renumber the triangulations 𝑇1 ∈ 𝑇𝑟(𝐹1, ∩ 𝐹1) and 𝑇2 ∈ 𝑇𝑟(𝐹2, ∩ 𝐹2). We now present some of the results obtained by the described methods. Example 1. Consider the set 𝐿𝑚,𝑛 on the plane, consisting of ·𝑚 points: 𝐿𝑚,𝑛 = {(𝑖, 𝑗) : = 1, 2,..., 𝑛, = 1, 2,...,𝑚}, where 𝑛,𝑚 ≥ 1 - integers. Let be the convex hull of = 𝐿𝑚,𝑛. Then the number of triangulations in 𝑇𝑟(𝐹, 𝑃) for some and we calculated in three ways: 1) Using algorithm from [1] for constructing all triangulations ∈ 𝑇𝑟(𝐹, 𝑃) (Algorithm 1). 2) Using algorithm we describe above, where 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). 3 4 4 4 6 4 5 6 Algorithm 1 12 6 3 963 More then 2 · 105 Algorithm 2 7 3 85 3 511 Algorithm 3 2 2 40 1 231 The number of triangulations 182 132 46 456 2 822 648 182 881 520 The table shows the operating time of the computer program (in seconds). Example 6. The following problem arises often: for given and we need to numbering only those triangulation ∈ 𝑇𝑟(𝐹, 𝑃), that satisfy certain additional conditions (Filtering problem). The following table shows (for some 𝑚, and ∈ R) the number of such a triangulation from Example 1, that for any triangle