4551
правка
Минимальные геометрические остовные деревья: различия между версиями
Перейти к навигации
Перейти к поиску
м
Минимальные геометрические остовные деревья (посмотреть исходный код)
Версия от 01:12, 19 декабря 2015
, 19 декабря 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 51: | Строка 51: | ||
Теорема. В модели алгебраического дерева вычислений для любой фиксированной <math>L_p</math>-метрики и любого фиксированного количества размерностей вычисление MST имеет ту же временную сложность в наихудшем случае, с поправкой на константный множитель, что и вычисление бихроматической пары ближайших точек. Кроме того, в трехмерном пространстве с метриками <math>L_1 \;</math> и <math>L_{\infty} \;</math> задача MST, также как и вычисление бихроматической пары ближайших точек, требуют оптимального времени вычисления O(n log n). | '''Теорема.''' В модели алгебраического дерева вычислений для любой фиксированной <math>L_p</math>-метрики и любого фиксированного количества размерностей вычисление MST имеет ту же временную сложность в наихудшем случае, с поправкой на константный множитель, что и вычисление бихроматической пары ближайших точек. Кроме того, в трехмерном пространстве с метриками <math>L_1 \;</math> и <math>L_{\infty} \;</math> задача MST, также как и вычисление бихроматической пары ближайших точек, требуют оптимального времени вычисления O(n log n). | ||
== Приближенные и динамические решения == | == Приближенные и динамические решения == | ||