Метод цепей для организации хранения многомерных триангуляций

О способах записи триангуляции

В настоящей статье под к -мерным симплексом S в R ” мы понимаем выпуклую оболочку к + 1 точек А г ,г = 0,..., к <  п таких, что векторы А 1 — А 0 ,А 2 — А 0 ,..., А ^ — А ₀ линейно независимы. Пусть р г ,г = 1,...,N — некоторый набор точек р г Е R ” таких, что любой симплекс в вершинах из { р ^ } является невырожденным. Триангуляцией Т заданного набора точек называется такой набор п -мерных симплексов S 1 ,...,S _m , что:

• 1)    каждая точка p _i заданного набора является вершиной одного из симплексов S Е Т ;

• 2)    каждая вершина любого симплекса S Е Т является одной из точек р^г = = 1,...,N ;

• 3)    внутренность пересечения любых двух симплексов пуста.

Один из первых алгоритмов триангуляции с использованием условия пустого шара был предложен Б.Н. Делоне в его работе [5] (перевод см.: [1]).

Нас будет интересовать вопрос об оценке объема памяти, необходимой для хранения триангуляции заданного набора точек. Отметим работу [4], в которой решается подобная задача для случая размерности п = 2 . Объем памяти будем вычислять в битах. С этой целью введем функцию Ь(х) , равную минимальному числу бит, необходимому для записи натурального числа х Е N в двоичной системе счисления. Очевидно, что

Ь(х) = [log 2 х] + 1.

Формально постановка задачи следующая. Обозначим через V(Р ) совокупность всех триангуляций набора точек Р = { р 1 ,р ₂ , ...,p _N } . Тогда под способом записи триангуляции Т мы понимаем отображение

/ : V(Р) ^ N, которое всякой триангуляции ставит в соответствие натуральное число. Причем, мы предполагаем, что отображение обладает свойством

V P ‘ = Р ‘‘ е V(Р ) ^ / (Р ‘ ) = / (Р ‘‘ ).

Тогда величину

^ ^{( /}) = тах _теУ (р ) Ь ^{( / ( Т} ))

можно считать мерой объема памяти, необходимой для запоминания триангуляции Т при заданном способе хранения / . Приведем примеры.

Пример 1. Один из стандартных способов (см., например, [2]) хранения триангуляции состоит в том, что каждому симплексу S _i Е Т сопоставляется набор из (п + 1) натурального числа п _{i 0} , п _{i 1} ,..., n _in , такой, что

^S i = C ^o nv [ p _{n j} 0 ,p _{n i}i , ...,Рщ _п ^} .

Значит, для такого способа записи одного симплекса понадобится (п + 1)&(^) бит, а для всей триангуляции получим величину т(п + 1)&(^) . В этом примере конструкция отображения / следующая. Значение /(Т) — это натуральное число, в двоичной системе записи которого первые b(N ) бит занимает число пю, вторые b(N ) бит — п 11 и т. д.

Другими словами, матрицу натуральных чисел Цп^||, г = 1,...,N, j = 0,

..

., п записы-

ваем в итоговое число построчно. Полученное натуральное число /(Т) будет в памяти занимать т(п + 1)b(N) бит. Обозначим построенное отображение в этом примере через /0. Заметим, что г      М(/о)          , з lim —----— = п + 1.

• n >^ mlog ₂ N

Мы предлагаем конструкцию построения отображения / , для которого

М ^{( /})

.lim n>^ mlog2N

= 1.

Для ее описания нам понадобится понятие цепи. Цепью С в заданной триангуляции Т Е V(Р ) мы назовем совокупность различных симплексов S 1 , S 2 , ..., S _k , такую, что для любого г = 2, ...,к симплексы S t - 1 и S t имеют единственную общую (п — 1) -мерную грань. Число к называется длиной цепи С . Предположим, что триангуляция Т Е V (Р ) разбита на непересекающиеся цепи С 1 , ...,С _Р длины 1 1 , ...,1 _Р соответственно. Пусть С — некоторая цепь. Построим последовательность натуральных чисел

П 10 ,П 11 , ...,П 1 _ТИХ 1 ,П 2 ,Х 2 ,П з , ...,Х _к- 1 ,п _к ,Х _к ,

где п ₁₀ ,п 11 ,...,п _{1 п} — номера вершин в диапазоне 1, 2,...,N первого симплекса цепи, х 1 — номер в диапазоне 0, 1,...,п вершины первого симплекса, напротив которого расположена общая грань со вторым симплексом, п ₂ — номер вершины второго симплекса, расположенной напротив общей грани с первым симплексом, и т. д. Причем х _к всегда равно п + 1 . Это число нам необходимо для указания конца цепи в последующих построениях. Несложно подсчитать, что для записи всей этой последовательности чисел понадобится (п + k)Ь(N) + кЬ(п + 1) бит. Так что для каждой цепи С _г мы получим запись длины (п + l _г )Ь(N ) + l _t Ь(п + 1) . Суммируя по всем цепям и используя равенство

р

1г = т, г=1

получим, что для всей записи симплексов триангуляции Т Е V(Р ) будет затрачено (рп + m)Ь(N )+ тЬ(п + 1) бит. Конструкция отображения / сводится к упаковке последовательностей вида (2) в одно двоичное число, содержащее ровно (рп+m)Ь(N)+тЬ(п+1) бит. Следовательно, для нашего отображения / получаем

р(/ ) = (рп + m)Ь(N ) + тЬ(п + 1).

Поэтому

..     р(/ )      ..   (рп + m)Ь(N )+ тЬ(п + 1)

lim —----— = lim -------------—-------- = 1, n>^ т1од2Л   n>^         т1од2Л при условии р = о(т), N ^ то, что предполагает неограниченное и равномерное увеличение длины цепей при N ^ то. На самом деле это условие несущественно, поскольку небольшие перестройки триангуляции позволяют записать ее в виде одной цепи. Однако представление триангуляции в виде одной цепи не разумно с точки зрения временных затрат на доступ к отдельному симплексу. Действительно, предложенная нами конструкция, скажем, в отличие от отображения /0 примера 1, не позволяет осуществить прямой доступ к любому симплексу, поскольку номера вершин формируются динамически — в процессе побитового чтения числа /(Т). При этом, чем длиннее цепь, тем она более затратней для чтения. Попытаемся найти оптимальное значение для количества цепей в триангуляции. Для этого составим целевую функцию. Пусть с1 — стоимость единицы одной операции доступа к памяти, с2 — стоимость одного бита памяти. Средняя длина цепи равна т/р, соответственно среднее число операций чтения равно т/2р. Получаем следующее выражение для целевой функции

F (р) = с 1-- + с ₂ (рп + m)Ь(N ) + тЬ(п + 1).

2р

Исследуя эту функцию на минимум, получим оптимальное значение для числа цепей

В этом случае

р

с1 m с2 2nb(N)'

ц(/ ) = а ^С ~ mnb(N ) + mb(N ) + mb(n + 1). V С 2

Так что и в оптимальном случае

Р ^{( /} )

. lim n>^ mlog2N

lim n ^^

у/ ^ 1 mnb(N) + mb(N) + mb(n + 1) mlog ₂ N

= 1.

Зададимся вопросом, насколько предложенный метод является наилучшим способом записи триангуляции. С этой целью необходимо получить нижние оценки величины ^(f) , независящие от / . Пусть К = | V (Р ) | обозначает мощность множества V(Р ) , то есть равно количеству триангуляций набора точек Р . Несложно проверить, что

Р ^{( /} ) >  [ ^lo g 2 ^{К ]} + 1.

Действительно, поскольку отображение / взаимно-однозначно, то мощность множества значений / равно мощности множества области определения, то есть в нашем случае эта мощность равна К . Это требует как минимум К натуральных чисел для идентификации каждой триангуляции. Для записи такого числа необходимо как минимум [log ₂ К ] + 1 бит.

Пример 2. Рассмотрим набор точек в R ² с координатами p _{i 0} = (г, 0) и Р г1 (г, 1) , где г = 0,1, ...,п . Так что N = 2(п + 1) . Триангуляцию будем строить так. Возьмем ребро р ₀₀ р ₀₁ . Для получения треугольника у нас два варианта: либо точка р ₁₀ , либо точка р 11 . Выберем какую-нибудь из них. Допустим, это точка р ₁₀ . Для получения следующего треугольника у нас опять два варианта: либо точка р ₂₀ , либо точка рц. Заметим, что во всех вариантах у нас будут две точки: одна на верхнем ряду, другая — на нижнем. Теперь отображение / можно построить так. Каждой триангуляции необходимо поставить в соответствие двоичное число длины 2п бит, в котором число единиц равно числу нулей. Единицы соответствуют выбору точки из верхнего ряда, а нули — из нижнего ряда. Так что всего комбинаций получается С П _п . Согласно формуле Стирлинга С П = о(4 ^п ) . Отсюда получаем оценку для числа триангуляций К = о(4 ^п ) , что, в свою очередь, учитывая, что число треугольников m = 2п , дает нулевое значение в пределе вида (1).

Пример 3. Рассмотрим N = п + 2 точки, лежащие в вершинах выпуклого N- угольника. Число триангуляций вершин выпуклого многоугольника дается числом

Ка-

талана (см., например, [7])

С п

п + 1

п

^С 2п *

Так что в этом случае ^(/) = о(4 ^п ) и мы получаем, как и в предыдущем примере,

Р ^{( /} )

. lim n>^ mlog2N

= 0 .

Оказывается, что эти примеры носят более общий характер. Именно в работах [3; 6; 8-11] было показано, что найдется абсолютная постоянная с, независящая от набора точек и его мощности N, что число триангуляций не превосходит cn. Наилучшая на данный момент константа с = 43 была найдена в работе [10]. Следовательно, можно надеяться на существование такого способа записи триангуляции, при котором число бит растет линейно при N ^ то. Ну и, в частности, будет выполнено (3).

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

Пусть F — многоугольник на плоскости и S = { р 1 ,р ₂ , ... ,P n } — такой набор точек плоскости, который включает все вершины многоугольника F , причем каждая точка р _г является или вершиной, или внутренней точкой F . Необходимо перечислить все триангуляции многоугольника F , вершинами которой являются точки множества S . Не теряя общности, считаем, что отрезок р 1 р ₂ является стороной многоугольника F .

Обозначения:

Триангуляция Т будет состоять из треугольников А 1 , А 2 , ... , А _т ( т — общее число треугольников в триангуляции).

Вершинами треугольника А & служат точки множества S с порядковыми номерами п1[к] , п2[к] и п3[к] .

к — порядковый номер строящегося треугольника из триангуляции Т . В начале построения к = 1 .

Треугольник строим следующим образом: к отрезку с порядковыми номерами точек п1[к] , п2[к] («активная сторона строящегося треугольника А & ») пытаемся подобрать вершину с порядковым номером п3[к] (если такая вершина существует) из того же множества S , и полученный треугольник А & будет включен в строющуюся триангуляцию Т . После этого ребро с концами п1[к] , п3[к] будет принято за активную сторону треугольника А ^ ₊ 1 , а ребро с концами п2[к] , п3[к] («свободное ребро») будет запомнено и в дальнейшем может быть использовано как активное ребро для построения треугольника А г при некотором г > к + 1 (если в этом возникнет необходимость).

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

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

Обозначения:

Очередная триангуляция Т будет состоять из треугольников А 1 , А ₂ , ... , А _т , где т — общее число треугольников в триангуляции (оно одинаково для любой триангуляции). Это число будет найдено после построения первой триангуляции. В начале работы алгоритма полагаем т = 0 . Вершинами треугольника А & служат точки множества S с порядковыми номерами п 1 [к] , п ₂ [к] и п ₃ [к] .

к — порядковый номер строящегося треугольника из триангуляции Т . В начале построения к = 1 .

Через В(г 1 ,г ₂ ,г ₃ ) будем обозначать треугольник с номерами вершин г 1 , г ₂ , г ₃ . Пусть к >  1 и треугольники А 1 , А 2 , ... , А ^ - 1 уже построены. Пусть г 1 , г ₂ , г ₃ — целые числа от 1 до п . Тогда через / (г 1 ,г ₂ ,г ₃ ) будем обозначать такое наименьшее целое число j , что г ₃ < j <  п и треугольник В(г 1 ,г ₂ , j ) можно добавить к последовательности А 1 , А 2 , ... , А ^ - 1 , то есть он удовлетворяет следующим условиям:

• (а)    В(г 1 ,г ₂ ,^) не содержит точек множества S , отличных от вершин этого треугольника;

• (b)    треугольник D (i₁,i₂ ,j ) не имеет общих внутренних точек ни с одним из треугольников А ₁ , А 2 , ... , А ^ _{- 1} (но может иметь общую вершину или общую сторону).

Если числа j с перечисленными свойствами не существует, то полагаем / (г ₁ ,г ₂ ,г ₃ ) = = 0 .

Определим функцию /(г ₁ ,г ₂ ,г ₃ ) и при к = 1 . А именно, /(г ₁ ,г ₂ ,г ₃ ) — это наименьшее целое число от 1 до п , которое больше г ₃ , и для которого треугольник D(i ₁ ,i ₂ ,j ) удовлетворяет условию (a). Если такого j не существует, то полагаем /(г ₁ ,г ₂ ,г ₃ ) = 0 .

В процессе работы алгоритма будут строиться также три одномерных массива 7 1 [г] , 7 2 [г] и /г[г] , где 1 <  г <  п . При построении треугольника А & отрезок е , , концами которого являются точки множества S с порядковыми номeрами д ₁ [г] и <7 2 [г] , г = 1, 2,..., к — 1 , в дальнейшем может быть использован для построения треугольника A _t , где t >  к . Отрезки е , содержатся в объединении границ треугольников А ₁ , А ₂ , ... , А д - ( е , — «граничные отрезки»). Массив /г[г] играет следующую роль: если /г[г] = 0 , то отрезок е , пока не использован для построения треугольника. Если же этот отрезок будет стороной некоторого треугольника A _t , t >  0 , включенного в строящуюся триангуляцию, то /г[г] = t .

На множестве упорядоченных пар целых чисел рассматриваем обычный лексикографический порядок: если a, b, c, d — целые числа, то

(a, b) < (c, d) < >  a <  c или (a = c и b < d).

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

• (1)    Полагаем к = 1 , п ₁ [1] = 1 , п ₂ [1] = 2 (активная сторона треугольника А ₁ ).

Триангуляция Т пока не содержит ни одного треугольника.

Полагаем m = 0 (число треугольников в триангуляции; оно будет определено после того, как будет построена первая триангуляция).

Полагаем ktr = 0 — общее число триангуляций.

• (2)    Начинаем строить треугольник А ^ (в этом пункте к >  1 — целое число). Полагаем п ₃ [к] = 0 .

• (3)    Полагаем j = /(п ₁ [к],п ₂ [к], п ₃ [к]) .

Если j = 0 , то идем к пункту (5), если же j >  0 , то идем к пункту (4).

• (4)    Принимаем за А д треугольник D(n ₁ [к],п ₂ [к], j) , где j — число, найденное в пункте (3), и определяем новую активную сторону с номерами вершин п ₁ [к] и п ₃ [к] . Для этого полагаем

^п з ^{[ к ]}        = ^j,

П 1 [к + 1] = П 1 [к], П 2 [к + 1] = п з [к].

Сторону с номерами вершин п ₂ [к] и п з [к] запоминаем как граничную сторону. Для этого полагаем

7 1 [к]   = П 2 [к],

7 2 [к]   = п з [к],

/г [к] = 0.

Число к увеличиваем на 1.

Если m = 0 , то идем к пункту (2).

Если m > 0 и к <  m , то идем к пункту (2).

Если m > 0 и к > m , то идем к пункту (7) (очередная триангуляция построена).

• (5)    На этот пункт попадем, если j = 0 в пункте (3). Среди граничных сторон выбираем такую, которую можно принять за активную сторону. Для этого полагаем

Е = { / : /<9 1 [/], 9 2 [/], 0) > 0, где 1 <  / < к } .

Если множество Е пусто, то идем к пункту (6). Если же Е = 0 , то за / 0 принимаем такое число, что (9 1 [/ ₀ ],9 2 [/ 0 ]) — наименьший элемент множества Е (относительно введенного выше лексикографического порядка). После выбора / 0 полагаем

^[к]   = 9 1 [/ о ],

^[к]   = 92 [/о], пз[к]   = 0,

/г[/ о ] = к.

Идем к пункту (3).

• (6)    На этот пункт попадем, если множество Е в пункте (5) пусто, то есть уже нет граничных ребер, которые можно принять за сторону строящегося треугольника. Это будет означать, что или построена очередная триангуляция, или зашли в тупик, или алгоритм завершил работу и все триангуляции уже перечислены. Действия в этом пункте таковы:

Если т = 0 , то полагаем т = к — 1 и идем к пункту (7).

Если к = 0 , то выдаем число ktr найденных триангуляций и завершаем работу.

Если 1 < к <  т , то к уменьшаем на 1 и идем к пункту (8).

• (7)    Построена очередная триангуляция. Выдаем список треугольников А 1 , А 2 ,..., А _т . Увеличиваем число ktr (уже построенных триангуляций) на 1 .

Переходим к построению очередной триангуляции. Для этого полагаем к = т — — 1 : в дальнейшем будем строить заново треугольник А _т-1 . Тем самым мы удаляем два последних построенных треугольника А _т-1 и А _т (удаление только последнего треугольника не даст новой триангуляции).

• (8)    Начинаем заново строить треугольник А ^ , а затем и все треугольники с большими номерами. При построении «старых» треугольников А ^ , А к₊₁ и т. д. могли быть использованы граничные ребра 9 1 [/] , 9 2 [/] . Теперь эти ребра снова должны стать граничными. Это достигается так: просматриваем массивы 9 1 [/] , 9 2 [/] , и если при некотором / верно 1 <  / < к и /г[/] >  к , то полагаем /г[/] = 0 — теперь при построении треугольника А- t , где t >  к , сторону с номерами вершин 9 1 [/] , 9 2 [/] можно будет использовать при построении треугольников А _- , где t >  к .

Полагаем j = /(п 1 [к],п ₂ [к],п ₃ [к]) .

Если j >  0 , то идем на пункт (3).

• (В противном случае) к уменьшаем на 1 .

Если к >  1 , то идем на пункт (8).

Полагаем j = /(п 1 [к],п ₂ [к],п ₃ [к]) .

Если j >  0 , то идем на пункт (8).

• (В противном случае) выдаем общее число кtr найденных триангуляций и завершаем работу.