Об алгоритме перечисления триангуляций

Вопросам построения триангуляций посвящена обширная литература (см., например, [2; 3]). В работе [1] предложен алгоритм построения всех триангуляций конечного множества на плоскости. В данной работе приводится модификация алгоритма для наборов точек трехмерного пространства.

Пусть Р = {р ₁ ,р ₂ , ... ,P n } — конечный набор точек в трехмерном пространстве. Необходимо перечислить все триангуляции этого набора. Под триангуляцией набора точек Р понимается такой набор тетраэдров S ₁ , S 2 , ... , S _k , для которого выполнены следующие условия:

• (1)    Каждая точка р _г Е Р является вершиной хотя бы одного из тетраэдров S j .

• (2)    Вершины любого тетраэдра S j лежат во множестве Р .

• (3)    Если г = 3 , то пересечение S ^ П S j или пусто, или является общей вершиной, или общим ребром, или общей гранью тетраэдров S ^ и S j .

• (4)    Объединение тетраэдров S ₁ , S 2 , ... , S k совпадает с выпуклой оболочкой conv(P) множества Р .

Под тетраэдром понимается выпуклая оболочка четырех точек (вершин тетраэдра), не лежащих в одной плоскости трехмерного пространства. Считаем, что точки множества Р не лежат в одной плоскости — иначе триангуляций этого множества не существует.

На множестве упорядоченных четверок целых чисел будем рассматривать лексикографический порядок:

• г ₁ < з 1 или

  ( ⁱ 1 ^,i 2 ^,i 3 ^,i 4 ⁾ <  ⁽ 3 1 ^,3 2 ^,3 3 ^,3 4 ⁾

  
  

  < >

  
  

ii = 31,г2 < 32 или ii = 31, ^2 = 32, гз <3з или

, i 1 = 3 1 , i 2 = 3 2 , i 3 = 3 3 ,i 4 <  3 4 .

Через S(i 1 ,i ₂ , i ₃ ,i ₄ ) будем обозначать тетраэдр S , вершинами которого являются точки Р с номерами i 1 , i ₂ , i ₃ и i ₄ . Таким образом, вершины S — это точки p _i 1 , p _{i 2} , p _{i 3} и p _{i 4} множества Р .

Будем говорить, что тетраэдр S совместим с тетраэдром S ‘ , если эти тетраэдры или не имеют общих точек, или же пересекаются по общей вершине, или по общему ребру, или по общей грани.

Сначала рассмотрим вспомогательный алгоритм А , который перечисляет все триангуляции, содержащие заданный тетраэдр.

1.    Алгоритм А

Пусть задан тетраэдр S 1 с вершинами из множества Р , не содержащий точек из Р , отличных от своих вершин. Опишем алгоритм А , который перечисляет все триангуляции Р , содержащие этот тетраэдр. На каждом шаге алгоритма будет определено число к построенных к данному моменту тетраэдров, а также два списка:

• 1)    Список 8 построенных тетраэдров S 1 , S 2 , ... , S _k . Каждый тетраэдр представлен в этом списке упорядоченной четверкой чисел (i 1 ,i ₂ ,i ₃ ,i ₄ ) , состоящей из номеров вершин этого тетраэдра.

• 2)    Список У граней тетраэдров из списка 8 . Каждая грань представлена упорядоченной тройкой (q 1 , q ₂ , q ₃ ) , состоящей из номеров вершин этой грани.

В список У помещаются такие грани, к которым в дальнейшем могут приклеиваться другие тетраэдры. Эти грани называются граничными. Если к граничной грани приклеивается тетраэдр, то грань становится внутренней. После удаления приклеенного тетраэдра грань снова становится граничной. В начале работы алгоритма списки 8 и У пусты.

Пусть вершинами тетраэдра S являются точки p _i 1 , p _{i 2} , p _{i 3} и p _{i 4} , то есть S 1 = = S (i 1 ,i ₂ ,i ₃ ,i ₄ ) . Алгоритм А состоит из следующих шагов:

• (1)    Полагаем к = 1 .

• (2)    Помещаем тетраэдр S 1 в список 8 (в качестве единственного элемента). Этот тетраэдр будет представлен в списке упорядоченной четверкой чисел (i 1 ,i ₂ ,i ₃ , i ₄ ) .

• (3)    Упорядоченные грани (i i ,i 2 ,i 3 ) , (i i ,i 2 ,i 4 ) , (i i ,i 3 ,i ₄ ) и (i 2 ,i 3 ,i 4 ) тетраэдра S i помещаем в список У и объявляем все эти грани граничными.

• (4)    Просматривая список У и давая переменной j значения 1, 2,..., N , пытаемся найти такую граничную грань (q 1 ,q ₂ ,q ₃ ) Е У и такое число j , 1 <  j < N , что тетраэдр S = S(q 1 ,q ₂ ,q ₃ ,j ) не содержит точек из Р , отличных от своих вершин, и совместим с каждым из тетраэдров списка 8 . Если нужной четверки чисел (q 1 ,q ₂ ,q ₃ ,j ) не найдено, то идем к пункту (6). Если же такая четверка есть, то переходим на пункт (5).

• (5)    Среди упорядоченных четверок чисел (q 1 ,q ₂ ,q ₃ ,j ) , удовлетворяющих условиям пункта (4), находим минимальную четверку (q^,q₂,q₃, j 0 ) (в смысле лексикографического порядка). За тетраэдр S _k+i принимаем S (q 0 ,q ₂ ,q ₃ ,j ⁰ ) . Далее осуществляем следующие действия:

• (a)    тетраэдр S _k+i (то есть четверку чисел (q 0 ,q 0 ,q 0 , j 0 ) ) помещаем в конец списка 8 ;

• (b)    три грани (q ⁰ ,q ⁰ ,j ⁰ ) , (q 0 ,q ⁰ ,j 0 ) и (q^q^j 0 ) тетраэдра S k+i помещаем в конец списка У . Объявляем эти грани граничными;

• (c)    грань (4₄,4₂,4₃) тетраэдра 8 ^+1 (находящуюся в списке У ) объявляем внутренней и запоминаем, что она была использована при построении тетраэдра S _{fc +}i ;

• (d)    увеличиваем к на 1;

• (e)    идем к пункту (4).

• (6)    Построена очередная триангуляция. Запоминаем данные об этой триангуляции. Счетчик числа триангуляций увеличиваем на 1.

• (7)    Из конца списка 8 удаляем тетраэдр 8 ^ , а из конца списка У удаляем три грани тетраэдра 8 ^ . Просматривая получившийся список У , находим четвертую грань тетраэдра 8 ^ и объявляем ее граничной.

• (8)    Уменьшаем к на 1.

• (9)    Пусть тетраэдр 8 ^ представлен в списке 8 упорядоченной четверкой чисел (i 1 , i ₂ ,i ₃ ,i ₄ ) . Давая переменной j значения i ₄ + 1,i ₄ + 2,..., N , пытаемся найти такое число j , что i ₄ < j < N , а тетраэдр 8 = 8(i 1 ,i ₂ ,i ₃ ,j ) , не содержащий точек из Р , отличных от своих вершин, и совместим с каждым из тетраэдров 8 1 , 8 ₂ , ... , 8 ^ - 1 из списка 8 .

Если число j с указанным свойством найдено, то идем к пункту (10).

Если нужное j не найдено, то при к >  2 идем к пункту (7), а при к = 2 идем к пункту (12).

• (10)    Полагаем 8^ = 8 = 8(i1, i₂, i₃, j), для чего в списке 8 последнюю четверку (i1,i₂,i₃,i₄) заменяем четверкой (i1, i₂, i₃, j). Кроме того, заменяем в списке У последние три грани (старого) тетраэдра 8^ гранями (i₁,i₂,j), (i1,i₃,j) и (i₂,i₃,j) (нового) тетраэдра 8^ = 8 = 8(i1 ,i₂,i₃,j) и объявляем все эти грани граничными.

• (11)    Идем к пункту (4).

• (12)    Конец работы.

2.    Алгоритм В

Пусть Р = {р 1 ,р ₂ ,... ,P n } — конечный набор точек в трехмерном пространстве. Алгоритм В перечисляет все триангуляции этого набора. Если все точки лежат в одной плоскости, то триангуляций нет. Пусть теперь выпуклая оболочка conv(P) множества Р — многогранник. Не теряя общности, считаем, что несколько первых вершин Р (а именно — вершины р 1 , р ₂ , ... , р^ и только они) лежат в одной грани G этого многогранника, а отрезок [р 1 ,р ₂ ] является ребром этой грани (или лежит на ребре) и не содержит точек из Р , отличных от р 1 и р ₂ .

Пусть Т — произвольная триангуляция множества Р . Тогда найдется (и единственен) входящий в эту триангуляцию тетраэдр 8 1 , одна из граней которого лежит в G , а р 1 и р ₂ являются вершинами этой грани. Ясно, что 8 1 имеет вид 8 (1,2,i ₃ ,i 4 ) , где 2 < i ₃ < kv и kv <  i ₄ <  п . Алгоритм В состоит из следующих шагов:

• (1)    Полагаем i ₃ = 3 .

• (2)    Полагаем i ₄ = kv + 1 .

• (3)    Если тетраэдр 8 = 8 (1, 2,i ₃ ,i 4 ) содержит точки из набора Р , отличные от своих вершин, то идем к пункту (5).

• (4)    Полагаем 8 1 = 8 и с помощью алгоритма А перечисляем все триангуляции, содержащие тетраэдр 8 1 .

• (5)    Увеличиваем г ₄ на 1 . Если / 4 <  N , то идем к пункту (3).

• (6)    Увеличиваем г ₃ на 1 . Если г ₃ <  кг) , то идем к пункту (2).

• (7)    Конец.

Замечание 6. Если какая-либо грань тетраэдра S 1 лежит на грани выпуклой оболочкой conv(F) множества Р , то при выполнении пункта (3) эту грань можно не заносить в список граничных граней, так как к ней нельзя будет в дальнейшем приклеить новый тетраэдр. Таким же образом можно поступать при выполнении подпункта (b) пункта (5). При этом, однако, надо будет запоминать номер того тетраэдра, гранью которого является грань, помещаемая в список У .

Отметим также, что если в пункте (4) алгоритма А не учитывать лексикографический порядок на множестве граней, то триангуляции могут повторяться.

Несложно убедиться, что алгоритм В перечисляет все триангуляции на Р . Проверим, что каждая триангуляция встретится ровно один раз. Пусть Т = S 1 , S 2 ,..., S _k и Т ‘ = S 1 , S 2 ,..., S ’ — две триангуляции, построенные на различных шагах алгоритма В . Покажем, что эти триангуляции различны. Если к = I , то это очевидно. Поэтому в дальнейшем считаем, что к = / .

Допустим, что S 1 = S 1 . По построению S 1 = (1,2,г ₃ ,г 4 ) и S 1 = (1,2,? 3 ,? 4 ) для некоторых i ₃ ,i ₄ ,i '₃ ,i ‘ 4 . При этом точки р 1 , р ₂ , p _{i з} и p _i ‘ лежат в грани G выпуклой оболочки conv(P) множества Р , а отрезок [р 1 ,р ₂ ] является ребром этой грани (или лежит на ребре). Кроме того, точки р 1 , р ₂ , p _{i 3} являются вершинами тетраэдра S 1 , а точки р 1 , р ₂ , p _i ‘ — вершинами тетраэдра S 1 . Поэтому пересечение тетраэдров S 1 и S 1 имеет внутренние точки и потому эти тетраэдры не могут входить в одну триангуляцию. Следовательно, Т = Т ‘ .

Пусть теперь S i = S 1 и S 2 = S 2 . Пусть S 2 = (q i ,q 2 ,q 3 ,j ) и S 2 = (q i , q 2 , q 3 ,j ‘ ) , где (q 1 , q ₂ , q ₃ ) и (q i , q' 2 ,q' ₃ ) — граничные грани тетраэдра S 1 . Допустим, что эти грани различны. Тогда одна из них, например, первая, меньше второй (при лексикографическом порядке). Но тогда при построении триангуляции Т ‘ в результате выполнения пунктов (4) и (5) алгоритма А за S 2 был бы принят тетраэдр S 2 — противоречие. Поэтому (q 1 ,q ₂ , q ₃ ) и (q i , q 2 , q 3 ) — одна и та же грань. При этом вершины р - и р - ’ лежат по одну сторону от этой грани. Поэтому тетраэдры S 2 и S 2 пересекаются по многограннику и потому не могут входить в одну триангуляцию. Следовательно, Т = Т ‘ . Продолжая подобные рассуждения, несложно убедиться, что Т = Т ‘ .

Описанные алгоритмы несложно модифицировать так, чтобы они были применимы для конечных наборов точек Р из пространства R ” , п >  3 . Для этого нужно вместо тетраэдров рассматривать симплексы размерности п .

Алгоритмы А и В позволяют получить, например, следующие результаты:

• (1)    Пусть Р — набор вершин куба. Тогда число триангуляций равно 74 .

• (2)    Пусть к вершинам куба добавлена точка на ребре куба. Тогда имеется 276 различных триангуляций.

• (3)    Пусть Р — набор вершин куба, к которому добавлен центр грани. Тогда число различных триангуляций равно 150 .

• (4)    Если к вершинам куба добавить середины двух соседних ребер, то число триангуляций увеличится до 1016 .

При получении очередной триангуляции можно провести анализ содержащихся в ней тетраэдров (при выполнении пункта (6) алгоритма А ). Пусть, например, а = а(Т ) — наименьший из плоских углов тетраэдров, входящих в триангуляцию Т . Тогда в случае

• (4)    a > 15 ° для всех 1016 триангуляций, 15 ° < а <  16 ° для 356 триангуляций, 18 ° <  < а <  19 ° для 612 триангуляций и а >  19 ° для 48 триангуляций.

Автор признателен В.А. Клячину за полезные обсуждения.