On a Generalization of the Delaunay Condition .pdf 1. Алгоритм построения триангуляции ДелонеПусть в пространстве Rn задан конечный набор точек M. Триангуляцией множества M называется разбиение выпуклой оболочки этого множества на n-мерные симплексы с вершинами в точках из M, у которых внутренности не пересекаются. Симплексом S в вершинах xo,xi,...,x„e Rn мы называем выпуклую оболочку точек x,. Симплекс S называется невырожденным, если векторы x1 - x0, x2 - x0,..., xn - x0 линейно независимы. В дальнейшем, будем рассматривать только такие наборы точек для которых любой симплекс в вершинах из P, является невырожденным.Прежде чем переходить к формулировкам указанных результатов, приведем схему алгоритма построения триангуляции Делоне в классическом варианте (см. [2]). Данная схема позволяет понять существенность теоремы о пустой сферы в указанном алгоритме. Мы следуем книге Шикина Е.В. и Борескова А.В. «Компьютерная графика. Полигональные модели» [2], модифицируя представленный там алгоритм на многомерный случай.Прежде всего, дадим одно свойство сфер, описанных вокруг симплексов. Рассмотрим два симплекса Si и S2, имеющих общую (п-1)-мерную грань G. Пусть A и В вершины симплексов, не принадлежащие грани G .Тогда, если сфера, описанная вокруг S1, не содержит внутри себя вершину B симплекса S2, то сфера, описанная вокруг S2, не содержит внутри себя вершины A. Действительно, пусть 2, - сфера, описанная вокруг S,. Пусть Е± - части, на которые разбиваются эти сферы и лежащие в полупространствах П±, определяемых плоскостью П, содержащей грань G. Будем предполагать, что вершина ВеП-, значит, B ёЕ- . Поэтому Е- лежитвнутри Е2 . Если предположить, что вершина A лежит внутри 22, то получается,что и вся сфера 21 лежит внутри сферы 22, касаясь этой сферы в n точках - вершинах грани G. Откуда следует, что сферы 22 и 21 совпадают. Это противоречит тому, что точка A, по предположению, лежит внутри сферы 22.Алгоритм состоит из ряда шагов, выполняющихся в цикле. Заметим, что в [3] проведен анализ других существующих алгоритмов, некоторые из которых используют теорему о неполноте сферы.•·Строится выпуклая оболочка данной системы точек P;, /=1,2,...,N. Предполагается, что никакие n точек данного семейства не лежат на одной гиперплоскости. В предположении, что никакие (n+1) точек не лежат на одной сфере, триангуляция Делоне строится единственным способом.•Выбирается n точек из данного семейства, лежащие на границе выпуклой оболочки conv(P), такие, что (п-1)-мерный симплекс G0 с вершинами в этих точках также лежит на границе выпуклой оболочки.•Ориентируем этот симплекс относительно внешней нормали к границе выпуклой оболочки conv(P). Находим точку из семейства такую, что описанная сфера вокруг полученного симплекса не содержит других точек из P .•Выбираем произвольную грань построенного симплекса, отличную от G0. Ориентируем эту грань нормалью, направленной в сторону уже построенного симплекса, содержащего эту грань. Из оставшихся точек находим точку из семейства P , такую, что сфера, описанная вокруг нового симплекса, построенного на вершинах грани G0 и найденной точке, не содержит необработанных точек семейства P . Свойство описанных сфер, приведенное в начале данного пункта статьи, и «фундаментальная теорема» Вороного-Делоне [1] обеспечивают «пустоту сферы» относительно и уже включенных в триангуляцию точек.•Далее процесс повторяется в цикле, пока не будут все точки включены в триангуляцию. Ориентация граней симплексов необходима для правильной организации этого цикла и поиска новых точек в предыдущем шаге цикла.2. Теорема о пустоте семейства выпуклых множествРассмотрим в Rn семейство выпуклых подмножеств F(x,r), xeRn, reR, и множество точек {р }f=0, расположенных в некоторой области D с Rn. Классическоеусловие Делоне и соответствующая теорема о пустоте сферы получаются как частный случай, если мы положим F(x,r) = {y е Rn: |y - x| < r}.Пусть S - произвольный невырожденный симплекс. Определим описанное множество (если оно существует) (S) из семейства F(x,r) как множество, чья граница содержит все вершины симплекса (значит, (S) содержит весь симплекс в силу выпуклости F(x,r)).Определение 1. Рассмотрим произвольную триангуляцию множества точек P;. Будем говорить, что триангуляция глобально равномерна относительно семейства F(x,r), если для любого симплекса S этой триангуляции внутренность множества (S) не содержит вершин других симплексов.Определение 2. Рассмотрим произвольную триангуляцию множества точек P . Будем говорить, что триангуляция локально равномерна относительно семействаF(x,r), если для любого симплекса S этой триангуляции внутренность множества (S) не содержит вершин других симплексов, имеющих общую (п-1)-мерную грань.Основным результатом работы является следующая теорема.Теорема 1. Для того чтобы для семейства выпуклых множеств F(x,r), xeRn, reR, из локальной равномерности следовала глобальная равномерность, достаточно, чтобы указанное семейство обладало свойством: для любого симплекса S существовало и было единственным описанное множество i^S).Доказательство. Рассмотрим некоторую триангуляцию множества точек P;, обладающую локальным свойством равномерности. Зафиксируем произвольный симплекс S данной триангуляции и вершину A произвольного симплекса, отличного от S. Поступая как и в [1], построим луч OA, соединяющий некоторую внутреннюю точку симплекса S и вершину A и пересекающий границы симплексов по их некоторым ^-^-мерным граням. Нам необходимо доказать, что вершина A не принадлежит внутренности множества i(S). Пусть S1v..SL - последовательность симплексов, которые пересекает луч OA, а Gb...,GL - соответствующие (n-1)-мерные грани, пересекаемые этим же лучом. Рассмотрим симплекс Si. Пусть zi-вершина этого симплекса, не принадлежащая симплексу S. Тогда, в силу локальной равномерности, вершина z1 не принадлежит (S). Пусть П1 - гиперплоскость, содержащая грань G1 и разбивающая пространство на полупространство П-,содержащее симплекс S, а также полупространство П+. Тогда, вершина A лежит в полупространстве П+. Предположим, что вершина A принадлежит симплексу S2. Тогда, если предположить, что вершина A лежит в 4>(S), то она должна принадлежать пересечению 0(S)nO(S1). Действительно, если это не так, то на части луча OA пП+ существуют точки, принадлежащие i(S) n i(S1), и также точки, не принадлежащие этому пересечению. Поэтому найдется точка B едФ(Б) n50(Sj) пП+ . Построим симплекс S ', вершинами которого являются вершины грани Gi, а также вершина B. Тогда найдутся два множества из семейства F(x,r), а именно 4>(S) и i(S1), описанные около S '. Последнее противоречит единственности описанного множества (S '). Таким образом, Aei(S)ni(S1). Но это противоречит локальной равномерности триангуляции относительно F(x,r). Аналогично, по индукции мы получаем, что вершина A не может лежать в 4>(S) при условии, что эта вершина одного из симплексов S,, i = 2,..., L. Теорема доказана.

Скачать электронную версию публикации