4551
правка
Планарные геометрические остовы: различия между версиями
Материал из WEGA
Планарные геометрические остовы (посмотреть исходный код)
Версия от 23:07, 30 января 2018
, 30 января 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 59: | Строка 59: | ||
'''Теорема 4. Пусть S – множество n точек на плоскости. Триангуляция Делоне для множества S содержит подграф с максимальной степенью не выше 17, являющийся t-остовом S для некоторого константного t. Если имеется триангуляция Делоне, этот подграф можно построить за время O(n).''' | '''Теорема 4. Пусть S – множество n точек на плоскости. Триангуляция Делоне для множества S содержит подграф с максимальной степенью не выше 17, являющийся t-остовом S для некоторого константного t. Если имеется триангуляция Делоне для S, этот подграф можно построить за время O(n).''' | ||
На самом деле результат оказался даже более общим: | На самом деле результат оказался даже более общим: | ||
