264
правки
Изменения
м
}}
{{Определение
|definition=
'''Локальный критерий Делоне:''' при построении плоскости через три точки, образующие треугольник, противолежащие сторонам треугольника вершины соседей лежат ниже этой плоскости.
}}
{{Определение
|definition=
'''Глобальный критерий Делоне для ребра:''' через ребро можно провести плоскость так, что все точки будут лежать ниже этой плоскости.
}}
{{Определение
|definition=
'''Локальный критерий Делоне для ребра:''' через ребро можно провести плоскость так, что вершины, противолежащие этому ребру, будут лежать ниже этой плоскости
Нет описания правки
|definition=
'''Критерий Делоне:''' при построении плоскости через три точки, образующие треугольник, все остальные точки лежат ниже этой плоскости.
}}
Триангуляция выпуклого многоугольника требует времени <tex> \mathcal{O}(k) </tex>, где <tex>k</tex> {{---}} число вершин с многоугольнике. Следовательно, в худшем случае нам потребуется суммарно <tex> \mathcal{O}(n) </tex> операции, чтоб перетриангулировать все грани, оказавшиеся многоугольниками после построения выпуклой оболочки.
Таким образом, время работы всего алгоритма будет <tex> \mathcal{O}n \log(n) </tex>
== Критерий Делоне для ребер==
{{Определение
|definition=
'''Глобальный критерий Делоне для ребра:''' через ребро можно провести плоскость так, что все точки будут лежать ниже этой плоскости.
}}
==Локальный критерий Делоне==
{{Определение
|definition=
'''Локальный критерий Делоне для ребра:''' через ребро можно провести плоскость так, что вершины, противолежащие этому ребру, будут лежать ниже этой плоскости
}}
{{Определение
|definition=
'''Локальный критерий Делоне:''' при построении плоскости через три точки, образующие треугольник, противолежащие сторонам треугольника вершины соседей лежат ниже этой плоскости.
}}
=Динамический алгоритм=
==Вставка точки==
