Триангуляция Делоне на сфере

НЯ! Эта статья полна любви и обожания. Возможно, стоит добавить ещё больше?

Определение

Определение:

Триангуляция — набор непересекающихся отрезков, соединениющий заданный набор точек так, что добавление новых отрезков невозможно без пересечения уже имеющихся.

Определение:

Отрезок — кратчайшее расстояние от точки до точки на заданной поверхности.

Определение:

Симплекс(англ. simplex) — геометрическая фигура, являющаяся n-мерным обобщением треугольника.

Определение:

Триангуляция — разбиение геометрической фигуры на симплексы.

Определение:

Критерий Делоне: при построении плоскости через три точки, образующие треугольник, все остальные точки лежат ниже этой плоскости.

Определение:

Локальный критерий Делоне: при построении плоскости через три точки, образующие треугольник, противолежащие сторонам треугольника вершины соседей лежат ниже этой плоскости.

Определение:

Критерий Делоне для ребра: через ребро можно провести плоскость так, что все точки будут лежать ниже этой плоскости.

Определение:

Локальный критерий Делоне для ребра: через ребро можно провести плоскость так, что вершины, противолежащие этому ребру, будут лежать ниже этой плоскости

Существования триангуляции Делоне

Лемма (1):

Сечение сферы плоскостью есть круг, а основание перпендикуляра проведенного из центра шара к пересекаемой плоскости есть центр круга, полученного в сечении.

Доказательство:

[math]\triangleright[/math]

Пусть плоскость [math]\alpha[/math] пересекает сферу. Из центра [math]O[/math] опустим перпендикуляр [math]OC[/math] на плоскость [math]\alpha[/math]. Соединим произвольную точку [math]M[/math] линии пересения плоскости [math]\alpha[/math] со сферой с точками [math]O[/math] и [math]C[/math]. Так как [math]OC[/math] ⊥ [math]\alpha[/math], то [math]OC[/math] ⊥ [math]CM[/math]. В прямоугольном треугольнике [math]OCM CM2 = OM2 - OC2[/math]. Т.к. [math]OM[/math] и [math]OC[/math] - величины постоянные, то и [math]CM[/math] - величина постоянная. Таким образом все точки линии пересечения плоскости [math]\alpha[/math] и сферы равноудалены от точки [math]C[/math], поэтому эта линия пересечения является окружностью с центром в точке [math]C[/math] и радиусом [math]r = CM[/math].

[math]\triangleleft[/math]

Теорема:

Триангуляция Делоне существует, причём для каждого набора точек, в котором никакие четыре точки не лежат на одной окружности она единственна.

Доказательство:

[math]\triangleright[/math]

Построим выпуклую оболочку наших точек. Все грани выпуклой оболочки окажутся внутри сферы. Поскольку, все точки лежат на сфере, не найдётся точек, которые будут лежать за гранями выпуклой оболочки, иначе выпуклую оболочку можно было бы расширить. Таким образом, все точки, будут принадлежать выпуклой оболочке. Так же ясно,что критерий Делоне будет выполняться, поскольку для каждой грани не будет точек, которые лежат выше нее. Поскольку никакие четыре точки не лежат на одной окружности в исходном наборе точек, а значит, гранями выпуклой оболочки будут треугольнички. Значит, триангуляция существует. А поскольку выпуклая оболочка единственна, можно сказать,что и триангуляция единственна.

[math]\triangleleft[/math]

Если случилось так, что у нас есть четыре или более точек, лежащих на одной окружности, то у построенной выпуклой оболочки, возможно, будут грани, не являющиеся треугольниками. Понятно, что такие грани будут выпуклыми многоугольниками. Тогда каждую из них можно затриангулировать методом отрезания "ушей". Получившиеся треугольники будут лежать в одной плоскости и,следовательно, не будут нарушать критерий Делоне. В этом случае триангуляция может быть не единственна.

Время работы

Мы можем построить выпуклую оболочку за [math] \mathcal{O}(n \log(n)) [/math], где [math]n[/math] — количество точек. Триангуляция выпуклого многоугольника требует времени [math] \mathcal{O}(k) [/math], где [math]k[/math] — число вершин с многоугольнике. Следовательно, в худшем случае нам потребуется суммарно [math] \mathcal{O}(n) [/math] операции, чтоб перетриангулировать все грани, оказавшиеся многоугольниками после построения выпуклой оболочки. Таким образом, время работы всего алгоритма будет [math] \mathcal{O}n \log(n) [/math]