23
правки
Изменения
Нет описания правки
Триангуляция выпуклого многоугольника требует времени <tex> \mathcal{O}(k) </tex>, где <tex>k</tex> {{---}} число вершин с многоугольнике. Следовательно, в худшем случае нам потребуется суммарно <tex> \mathcal{O}(n) </tex> операции, чтоб перетриангулировать все грани, оказавшиеся многоугольниками после построения выпуклой оболочки.
Таким образом, время работы всего алгоритма будет <tex> \mathcal{O}n \log(n) </tex>
== Критерий Делоне для ребер==
{{Определение
|definition=
'''Глобальный критерий Делоне для ребра:''' через ребро можно провести плоскость так, что все точки будут лежать ниже этой плоскости.
}}
{{Утверждение
|id=krit_dol1
|statement=Глобальный и локальный критерии Делоне для треугольника равносильны.
|proof=Предположим противное, в секторе у ребра <tex>AB</tex> нашли множество точек из триангуляции. Треугольник <tex>ADB</tex> смежный, при том точка <tex>D</tex> лежит под окружностью. Рассмотрим точку <tex>E</tex> из того множества. Так как <tex>AB</tex> является пересечением плоскостей <tex>ABC</tex> и <tex>ADB</tex>, точка <tex>D</tex> лежит под плоскостью <tex>ABC</tex>, а точка <tex>E</tex> над ней => точка <tex>E</tex> лежит над плоскостью <tex>ADB</tex>. Если треугольник <tex>AED</tex> не существует, то повторим итерацию, иначе для треугольника <tex>ADB</tex> не будет выполняться локальный критерий.
}}
|definition=
'''Локальный критерий Делоне:''' при построении плоскости через три точки, образующие треугольник, противолежащие сторонам треугольника вершины соседей лежат ниже этой плоскости.
}}
{{Утверждение
|id=krit_dol2
|statement=Глобальный и локальный критерии Делоне для ребра равносильны.
|proof=Из глобального в локальный очевидно, докажем обратно.
Предположим противное, то есть найдётся такая плоскость, что вершины треугольников при ребре <tex>AB</tex> лежат под ней, но существует какая-то вершина <tex>F</tex> над ней. Проведём окружность с центром в сфере через <tex>AB</tex> и выберем треугольник лежащий в одной полусфере с точкой <tex>F</tex>, назовём его <tex>ABC</tex>. Точка <tex>E</tex> лежит над плоскостью <tex>ABC</tex> => <tex>E</tex> лежит внутри окружности около <tex>ABC</tex>. Возьмем треугольника при ребре, в чьем сегменте оказалась точка <tex>E</tex> и назовем его <tex>ABC</tex>. Если не существует смежный с ним треугольник при вершине <tex>E</tex>, то повторим итерацию, иначе противоречие с локальным критерием Делоне.
}}
{{Утверждение
|id=krit_dol3
|statement=Критерии Делоне для ребер и треугольников равносильны.
|proof=Из треугольника в ребра: если для каждого треугольника выполнен критерий, то для каждого ребра можно рассматривать плоскость при любом треугольнике при ребре.
Обратно: Рассмотрим треугольник <tex>ABC</tex>, для каждого из ребра можно провести плоскость и они образуют трехмерный угол, снаружи которого нет точек. В пересечении угла и плосокости <tex>ABC</tex> образуется тетраэдр. Если в нем есть точки, то точки есть внутри треугольника, тогда это не триангуляция => точек в тетраэдре нет => плоскостью <tex>ABC</tex> можно отделить пространство с точками => выполняется глобальный критерий.
}}
==Динамический алгоритм==
