4. Триангуляции многоугольника на плоскости

  Пусть �� — замкнутый многоугольник на плоскости и �� = {��1, ��2, . . ., ����} — такое его конечное подмножество, которое содержит все вершины ��. Необходимо перечислить все триангуляции многоугольника ��, вершинами которых являются точки множества ��. Алгоритм решения этой задачи описан в [3]. Дадим альтернативное описание этого алгоритма. Не теряя общности, будем считать, что отрезок [��1, ��2] является стороной многоугольника ��.

  Рассмотрим дерево ��, вершинами которого являются такие упорядоченные наборы Д1, Д2, . . ., Д�� треугольников с вершинами из множества ��, объединение которых является связным множеством и которые можно достроить до триангуляции на �� путем добавления (справа) других треугольников (с вершинами из ��), или эти наборы уже сами являются триангуляциями на ��. Кроме того, дерево �� содержит пустой набор ∅,

который является корнем дерева. Пусть �� = Д1, Д2, . . ., Д�� и �� = Д′1, Д′2, . . ., Д′�� две вершины дерева ��. Тогда из вершины �� в вершину �� идет дуга тогда и только тогда, когда �� = �� + 1 и Д�� = Д′�� при �� = 1, 2, . . ., ��. Иными словами, (��, ��) — дуга в том и только том случае, когда набор �� получается из набора �� путем добавления в конец набора �� некоторого треугольника. Триангуляциям многоугольника �� (с дополнительными точками из ��) соответствуют листья дерева ��.

  Пусть �� = Д1, Д2, . . ., Д�� — вершина дерева ��, не являющаяся триангуляцией. Тогда из �� выходит хотя бы одна дуга. Введем на множестве дуг, выходящих из ��, отношение порядка «≺». Пусть имеется две дуги (��, ��) и (��, ��′). Тогда �� и ��′ получаются из набора �� путем добавления в конец набора Д��+1 и Д′��+1

некоторых треугольников Д��+1 и Д′��+1

соответственно. Эти треугольники имеют общие отрезки с некоторыми треугольниками набора ��. Пусть ��, �� и ��′, ��′ — номера вершин этих отрезков. Не теряя общности, считаем, что �� < �� и ��′ < ��′. Пусть также �� и ��′ — номера третьих вершин треугольников Д��+1 и Д′��+1. Тогда считаем, что (��, ��) ≺ (��, ��′) в том и только том случае, когда �� < ��′

или когда �� = ��′ и �� < ��′ или когда �� = ��′, �� = ��′ и �� < ��′. Таким образом, «≺» является модификацией лексикографического порядка.

  Напомним, что нумерация вершин множества �� такова, что отрезок [��1, ��2] является стороной многоугольника ��.

4. Polygon triangulation on a plane

  Let �� be a closed polygon on the plane, and �� = {��1, ��2, . . ., ����}, which is its finite subset that contains all vertices of ��. It is necessary to specify all triangulations of polygon �� with its vertices being represented by points from the set ��. The algorithm for solving this problem is described in [3]. We provide an alternative des cription of this algorithm. Without losing generality, we consider the segment [��1, ��2] as a side of polygon ��.

  Consider the tree �� with its vertices represented by the ordered set of Д1, Д2, . . ., Д�� of triangles with vertices from the set ��. The union of these sets is a connected set. The sets can be completed into the triangulation on �� by adding (to the right) other triangles (with vertices from ��). Alternatively, these sets are already the triangulations on ��. Additionally, the tree �� contains a null set ∅, which is the root of the tree. Let �� = Д1, Д2, . . ., Д�� and �� = Д′1, Д′2, . . ., and Д′�� is the two vertices of the tree ��. Then, a curve goes from vertex �� to vertex �� only if �� = �� + 1 and if Д�� = Д′�� at �� = 1, 2, . . ., ��. Thus, (��, ��) is an arc only if the set �� is obtained from the set �� by adding a triangle at the end of the set ��. The leaves of the tree of �� correspond to the triangulations of polygon �� (with additional points from ��).

  Let �� = Д1, Д2, . . ., Д��, which is the vertex of the tree �� that is not a triangulation. Then, at least one arc originates from ��. We introduce an order relation “≺” on the set of arcs that originate from ��. Let there be two arcs (��, ��) and (��, ��′). Then, �� and ��′ are obtained from the set �� by adding triangles Д��+1 and Д′��+1 to the end of set Д��+1 and Д′��+1, respectively. These triangles have common segments with triangles of the set ��. Let ��, �� and ��′, ��′ be the numbers of the vertices of these segments. Without losing generality, we consider that �� < �� and ��′ < ��′. Additionally, let �� and ��′ be the numbers of the third vertices of triangles Д��+1 and Д′��+1. Then, we consider that (��, ��) ≺ (��, ��′) only if �� < ��′ or when �� = ��′ and �� < ��′ or when �� = ��′, �� = ��′ and �� < ��′. Thus, “≺” is a modification of a lexicographical order.

  Furthermore, the numbering of the vertices from the set �� is such that the segment [��1, ��2] is a side of polygon ��.