close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
МАТЕМАТИКА
УДК 517.518.85+517.27
ББК 22.144
ОБ АЛГОРИТМЕ ПЕРЕЧИСЛЕНИЯ ТРИАНГУЛЯЦИЙ
Попов Владимир Валентинович
Кандидат физико-математических наук, доцент кафедры компьютерных наук и
экспериментальной математики, Волгоградский государственный университет
popov_v_v@rambler.ru, knem03@mail.ru, kiem@volsu.ru
просп. Университетский, 100, 400062 г. Волгоград, Российская Федерация
Аннотация. Описывается алгоритм перебора всех триангуляций конечного набора точек трехмерного пространства. Приводятся некоторые результаты работы компьютерной программы, составленной по этому алгоритму. Обсуждается вопрос о распространении алгоритма на пространства размерности
больше 3.
© Попов В.В., 2014
Ключевые слова: триангуляция, тетраэдр, симплекс, число триангуляций, выпуклая оболочка.
Вопросам построения триангуляций посвящена обширная литература (см., например, [2; 3]). В работе [1] предложен алгоритм построения всех триангуляций конечного
множества на плоскости. В данной работе приводится модификация алгоритма для наборов точек трехмерного пространства.
Пусть  = {1 , 2 , . . . ,  } — конечный набор точек в трехмерном пространстве.
Необходимо перечислить все триангуляции этого набора. Под триангуляцией набора
точек  понимается такой набор тетраэдров 1 , 2 , . . .,  , для которого выполнены
следующие условия:
(1) Каждая точка  ∈  является вершиной хотя бы одного из тетраэдров  .
(2) Вершины любого тетраэдра  лежат во множестве  .
(3) Если  ̸=  , то пересечение  ∩  или пусто, или является общей вершиной,
или общим ребром, или общей гранью тетраэдров  и  .
(4) Объединение тетраэдров 1 , 2 , . . .,  совпадает с выпуклой оболочкой conv( )
множества  .
Под тетраэдром понимается выпуклая оболочка четырех точек (вершин тетраэдра),
не лежащих в одной плоскости трехмерного пространства. Считаем, что точки множества  не лежат в одной плоскости — иначе триангуляций этого множества не существует.
На множестве упорядоченных четверок целых чисел будем рассматривать лексикографический порядок:
⎧
1 < 1 или
⎪
⎪
⎨
1 = 1 , 2 < 2 или
(1 , 2 , 3 , 4 ) ≤ (1 , 2 , 3 , 4 ) ⇐⇒
 = 1 , 2 = 2 , 3 < 3 или
⎪
⎪
⎩ 1
1 = 1 , 2 = 2 , 3 = 3 , 4 ≤ 4 .
40
ISSN 2222-8896. Вестн. Волгогр. гос. ун-та. Сер. 1, Мат. Физ. 2014. № 5 (24)
МАТЕМАТИКА
Через (1 , 2 , 3 , 4 ) будем обозначать тетраэдр ̃︀, вершинами которого являются точки
 с номерами 1 , 2 , 3 и 4 . Таким образом, вершины ̃︀ — это точки 1 , 2 , 3 и 4
множества  .
Будем говорить, что тетраэдр  совместим с тетраэдром  ′ , если эти тетраэдры
или не имеют общих точек, или же пересекаются по общей вершине, или по общему
ребру, или по общей грани.
Сначала рассмотрим вспомогательный алгоритм , который перечисляет все триангуляции, содержащие заданный тетраэдр.
1. Алгоритм 
Пусть задан тетраэдр 1 с вершинами из множества  , не содержащий точек из  ,
отличных от своих вершин. Опишем алгоритм , который перечисляет все триангуляции
 , содержащие этот тетраэдр. На каждом шаге алгоритма будет определено число 
построенных к данному моменту тетраэдров, а также два списка:
1) Список ℰ построенных тетраэдров 1 , 2 , . . .,  . Каждый тетраэдр представлен в этом списке упорядоченной четверкой чисел (1 , 2 , 3 , 4 ), состоящей из номеров
вершин этого тетраэдра.
2) Список ℱ граней тетраэдров из списка ℰ . Каждая грань представлена упорядоченной тройкой (1 , 2 , 3 ), состоящей из номеров вершин этой грани.
В список ℱ помещаются такие грани, к которым в дальнейшем могут приклеиваться другие тетраэдры. Эти грани называются граничными. Если к граничной грани
приклеивается тетраэдр, то грань становится внутренней. После удаления приклеенного
тетраэдра грань снова становится граничной. В начале работы алгоритма списки ℰ и ℱ
пусты.
Пусть вершинами тетраэдра  являются точки 1 , 2 , 3 и 4 , то есть 1 =
= (1 , 2 , 3 , 4 ). Алгоритм  состоит из следующих шагов:
(1) Полагаем  = 1.
(2) Помещаем тетраэдр 1 в список ℰ (в качестве единственного элемента). Этот
тетраэдр будет представлен в списке упорядоченной четверкой чисел (1 , 2 , 3 , 4 ).
(3) Упорядоченные грани (1 , 2 , 3 ), (1 , 2 , 4 ), (1 , 3 , 4 ) и (2 , 3 , 4 ) тетраэдра 1
помещаем в список ℱ и объявляем все эти грани граничными.
(4) Просматривая список ℱ и давая переменной  значения 1, 2, . . . ,  , пытаемся
найти такую граничную грань (1 , 2 , 3 ) ∈ ℱ и такое число  , 1 ≤  ≤  , что тетраэдр
̃︀ = (1 , 2 , 3 , ) не содержит точек из  , отличных от своих вершин, и совместим с
каждым из тетраэдров списка ℰ . Если нужной четверки чисел (1 , 2 , 3 , ) не найдено,
то идем к пункту (6). Если же такая четверка есть, то переходим на пункт (5).
(5) Среди упорядоченных четверок чисел (1 , 2 , 3 , ), удовлетворяющих условиям пункта (4), находим минимальную четверку (10 , 20 , 30 ,  0 ) (в смысле лексикографического порядка). За тетраэдр +1 принимаем (10 , 20 , 30 ,  0 ). Далее осуществляем
следующие действия:
(a) тетраэдр +1 (то есть четверку чисел (10 , 20 , 30 ,  0 )) помещаем в конец
списка ℰ ;
(b) три грани (10 , 20 ,  0 ), (10 , 30 ,  0 ) и (20 , 30 ,  0 ) тетраэдра +1 помещаем
в конец списка ℱ . Объявляем эти грани граничными;
ISSN 2222-8896. Вестн. Волгогр. гос. ун-та. Сер. 1, Мат. Физ. 2014. № 5 (24)
41
МАТЕМАТИКА
(c) грань (10 , 20 , 30 ) тетраэдра +1 (находящуюся в списке ℱ ) объявляем
внутренней и запоминаем, что она была использована при построении
тетраэдра +1 ;
(d) увеличиваем  на 1;
(e) идем к пункту (4).
(6) Построена очередная триангуляция. Запоминаем данные об этой триангуляции.
Счетчик числа триангуляций увеличиваем на 1.
(7) Из конца списка ℰ удаляем тетраэдр  , а из конца списка ℱ удаляем три
грани тетраэдра  . Просматривая получившийся список ℱ , находим четвертую грань
тетраэдра  и объявляем ее граничной.
(8) Уменьшаем  на 1.
(9) Пусть тетраэдр  представлен в списке ℰ упорядоченной четверкой чисел
(1 , 2 , 3 , 4 ). Давая переменной  значения 4 + 1, 4 + 2, . . . ,  , пытаемся найти такое
число  , что 4 <  ≤  , а тетраэдр ̃︀ = (1 , 2 , 3 , ), не содержащий точек из  ,
отличных от своих вершин, и совместим с каждым из тетраэдров 1 , 2 , . . ., −1 из
списка ℰ .
Если число  с указанным свойством найдено, то идем к пункту (10).
Если нужное  не найдено, то при  > 2 идем к пункту (7), а при  = 2 идем к пункту
(12).
(10) Полагаем  = ̃︀ = (1 , 2 , 3 , ), для чего в списке ℰ последнюю четверку
(1 , 2 , 3 , 4 ) заменяем четверкой (1 , 2 , 3 , ). Кроме того, заменяем в списке ℱ последние три грани (старого) тетраэдра  гранями (1 , 2 , ), (1 , 3 , ) и (2 , 3 , ) (нового)
тетраэдра  = ̃︀ = (1 , 2 , 3 , ) и объявляем все эти грани граничными.
(11) Идем к пункту (4).
(12) Конец работы.
2. Алгоритм ℬ
Пусть  = {1 , 2 , . . . ,  } — конечный набор точек в трехмерном пространстве.
Алгоритм ℬ перечисляет все триангуляции этого набора. Если все точки лежат в одной
плоскости, то триангуляций нет. Пусть теперь выпуклая оболочка conv( ) множества
 — многогранник. Не теряя общности, считаем, что несколько первых вершин  (а
именно — вершины 1 , 2 , . . .,  и только они) лежат в одной грани  этого многогранника, а отрезок [1 , 2 ] является ребром этой грани (или лежит на ребре) и не
содержит точек из  , отличных от 1 и 2 .
Пусть  — произвольная триангуляция множества  . Тогда найдется (и единственен) входящий в эту триангуляцию тетраэдр 1 , одна из граней которого лежит в ,
а 1 и 2 являются вершинами этой грани. Ясно, что 1 имеет вид (1, 2, 3 , 4 ), где
2 < 3 ≤  и  < 4 ≤ . Алгоритм ℬ состоит из следующих шагов:
(1) Полагаем 3 = 3.
(2) Полагаем 4 =  + 1.
(3) Если тетраэдр ̃︀ = (1, 2, 3 , 4 ) содержит точки из набора  , отличные от своих
вершин, то идем к пункту (5).
(4) Полагаем 1 = ̃︀ и с помощью алгоритма  перечисляем все триангуляции,
содержащие тетраэдр 1 .
42
В.В. Попов. Об алгоритме перечисления триангуляций
МАТЕМАТИКА
(5) Увеличиваем 4 на 1. Если 4 ≤  , то идем к пункту (3).
(6) Увеличиваем 3 на 1. Если 3 ≤  , то идем к пункту (2).
(7) Конец.
Замечание 6. Если какая-либо грань тетраэдра 1 лежит на грани выпуклой оболочкой
conv( ) множества  , то при выполнении пункта (3) эту грань можно не заносить в
список граничных граней, так как к ней нельзя будет в дальнейшем приклеить новый
тетраэдр. Таким же образом можно поступать при выполнении подпункта (b) пункта
(5). При этом, однако, надо будет запоминать номер того тетраэдра, гранью которого
является грань, помещаемая в список ℱ .
Отметим также, что если в пункте (4) алгоритма  не учитывать лексикографический порядок на множестве граней, то триангуляции могут повторяться.
Несложно убедиться, что алгоритм ℬ перечисляет все триангуляции на  . Проверим, что каждая триангуляция встретится ровно один раз. Пусть  = 1 , 2 , . . . ,  и
 ′ = 1′ , 2′ , . . . , ′ — две триангуляции, построенные на различных шагах алгоритма
ℬ . Покажем, что эти триангуляции различны. Если  ̸= , то это очевидно. Поэтому в
дальнейшем считаем, что  = .
Допустим, что 1 ̸= 1′ . По построению 1 = (1, 2, 3 , 4 ) и 1′ = (1, 2, ′3 , ′4 ) для
некоторых 3 , 4 , ′3 , ′4 . При этом точки 1 , 2 , 3 и ′3 лежат в грани  выпуклой
оболочки conv( ) множества  , а отрезок [1 , 2 ] является ребром этой грани (или
лежит на ребре). Кроме того, точки 1 , 2 , 3 являются вершинами тетраэдра 1 , а
точки 1 , 2 , ′3 — вершинами тетраэдра 1′ . Поэтому пересечение тетраэдров 1 и 1′
имеет внутренние точки и потому эти тетраэдры не могут входить в одну триангуляцию.
Следовательно,  ̸=  ′ .
Пусть теперь 1 = 1′ и 2 ̸= 2′ . Пусть 2 = (1 , 2 , 3 , ) и 2′ = (1′ , 2′ , 3′ ,  ′ ),
где (1 , 2 , 3 ) и (1′ , 2′ , 3′ ) — граничные грани тетраэдра 1 . Допустим, что эти грани
различны. Тогда одна из них, например, первая, меньше второй (при лексикографическом порядке). Но тогда при построении триангуляции  ′ в результате выполнения
пунктов (4) и (5) алгоритма  за 2′ был бы принят тетраэдр 2 — противоречие.
Поэтому (1 , 2 , 3 ) и (1′ , 2′ , 3′ ) — одна и та же грань. При этом вершины  и  ′
лежат по одну сторону от этой грани. Поэтому тетраэдры 2 и 2′ пересекаются по
многограннику и потому не могут входить в одну триангуляцию. Следовательно,  ̸=  ′ .
Продолжая подобные рассуждения, несложно убедиться, что  ̸=  ′ .
Описанные алгоритмы несложно модифицировать так, чтобы они были применимы
для конечных наборов точек  из пространства R ,  > 3. Для этого нужно вместо
тетраэдров рассматривать симплексы размерности .
Алгоритмы  и ℬ позволяют получить, например, следующие результаты:
(1) Пусть  — набор вершин куба. Тогда число триангуляций равно 74.
(2) Пусть к вершинам куба добавлена точка на ребре куба. Тогда имеется 276
различных триангуляций.
(3) Пусть  — набор вершин куба, к которому добавлен центр грани. Тогда число
различных триангуляций равно 150.
(4) Если к вершинам куба добавить середины двух соседних ребер, то число триангуляций увеличится до 1016.
При получении очередной триангуляции можно провести анализ содержащихся в
ней тетраэдров (при выполнении пункта (6) алгоритма ). Пусть, например,  = ( ) —
наименьший из плоских углов тетраэдров, входящих в триангуляцию  . Тогда в случае
ISSN 2222-8896. Вестн. Волгогр. гос. ун-та. Сер. 1, Мат. Физ. 2014. № 5 (24)
43
МАТЕМАТИКА
(4)  > 15 для всех 1016 триангуляций, 15 <  < 16 для 356 триангуляций, 18 <
<  < 19 для 612 триангуляций и  > 19 для 48 триангуляций.
Автор признателен В.А. Клячину за полезные обсуждения.
СПИСОК ЛИТЕРАТУРЫ
1. Клячин, В.␣А. Метод цепей для организации хранения многомерных триангуляций
/ В.␣А. Клячин, В.␣В. Попов // Вестник Волгоградского государственного университета.
Серия 1, Математика. Физика. — 2013. — № 2 (19). — C. 71–79.
2. Препарата, Ф. Вычислительная геометрия: Введение / Ф. Препарата, М. Шеймос. —
М. : Мир, 1989. — 478 c.
3. Скворцов, А.␣В. Триангуляция Делоне и ее применение / А.␣В. Скворцов. — Томск :
Изд-во Том. ун-та, 2002. — 128 c.
REFERENCES
1. Klyachin V.A., Popov V.V. Mеtod tsеpеy dlya organizatsii khranеniya mnogomеrnykh
triangulyatsiy [Chanes Method For Storage of Multidimensional Triangulation]. Vеstnik
Volgogradskogo gosudarstvеnnogo univеrsitеta. Sеriya 1, Matеmatika. Fizika [Science Journal
of Volgograd State University. Mathematics. Phisics], 2013, no. 2 (19), pp. 71–79.
2. Prеparata F., Shеymos M. Vychislitеlnaya gеomеtriya: Vvеdеniе [Computational
Geometry. An Introduction]. Moscow, Mir Publ., 1989. 478 p.
3. Skvortsov A.V. Triangulyatsiya Dеlonе i ее primеnеniе [Delaunay Triangulation and
its Application]. Tomsk, Izd-vo Tom. un-ta Publ., 2002. 128 p.
ON ALGORITHM OF NUMBERING OF TRIANGULATIONS
Popov Vladimir Valеntinovich
Candidate of Physical and Mathematical Sciences, Associate Professor, Department of
Computer Sciences and Experimental Mathematics,
Volgograd State University
popov_v_v@rambler.ru, knem03@mail.ru, kiem@volsu.ru
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  = {1 , 2 , . . . ,  } is a finite set of points in three-dimensional space.
The triangulation of this set is such a sequence 1 , 2 , . . .,  of tetrahedrons
with vertexs from  , which union is equal to convex hull conv( ) of  , and the
intersection  ∩  ,  ̸=  is or empty, or is the common vertex or the common
edge or the common face of tetrahedrons  and  , and each point  is the
vertex of some  .
At first, the algorithm  is described, which gives us the list of all
triangulations on  , containing some tetrahedron 1 with vertexs from a set
of  without points from  other than his vertexs. Let at some  the list of
tetrahedrons be already defined 1 , 2 , . . .,  which can be completed to some
triangulations for  , but the union  = 1 ∪ 2 ∪ . . . ∪   is not equal to
conv(P). Then there will be such two-dimensional face  a set  and such
44
В.В. Попов. Об алгоритме перечисления триангуляций
МАТЕМАТИКА
tetrahedron of  with vertexs from  which doesn’t contain points of a set 
other than his vertexs, and  ∩  =  . Among tetrahedrons  , which can be
constructed by this way, we choise such  , that the sequence (1 , 2 , 3 , 4 ) of
numbers of his vertex has a minimum value with respect to lexicographic order.
Now we put +1 =  . After some such a steps we get a triangulation of  . To
build other triangulations it is necessary to delete tetrahedrons with big numbers
and add new tetrahedrons before receiving new triangulations.
Let  be a boundary of the set conv( ). We assume that  ∩  =
= {1 , 2 , . . . ,  }, where  ≥ 3. and segment [1 , 2 ] doesn’t contains some points
from  other than 1 and 2 . Let 2 < 3 ≤  < 4 and  is the tetrahedrons with
vertexes 1 , 2 ,3 ,4 , which does not containes the points from  other than his
vertexs. Applying algorithm  to  , we obtain some triangulations of a set  .
Changing 3 , 4 , we get all the triangulations. By this way we realies algorithm
.
Algorithms  and ℬ allows us to receive, for example, the following results:
(1) Let  is the set of vertexs of a cube. Then the number of triangulations
of  is equall 74.
(2) Let  ′ =  ∪ {}, where  is the point of the edge of cube. Then  ′ has
276 triangulations.
Key words: triangulation, tetrahedron, simplex, number of triangulations,
convex hull.
ISSN 2222-8896. Вестн. Волгогр. гос. ун-та. Сер. 1, Мат. Физ. 2014. № 5 (24)
45
Документ
Категория
Без категории
Просмотров
4
Размер файла
310 Кб
Теги
алгоритм, триангуляции, перечисление
1/--страниц
Пожаловаться на содержимое документа