4446
правок
Геометрические остовы: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 116: | Строка 116: | ||
'''Остовы с препятствиями''' | '''Остовы с препятствиями''' | ||
Граф видимости на множестве попарно непересекающихся многоугольников называется графом взаимовидимых областей. Каждая | [[Visibility graph|Граф видимости]] на множестве попарно непересекающихся многоугольников называется ''графом взаимовидимых областей''. Каждая вершина многоугольника является вершиной в графе, а каждое ребро представляет видимую связь между ними: если две вершины видят друг друга, между ними строится ребро. Этот граф полезен благодаря тому, что содержит кратчайший путь, огибающий препятствия, между парой любых вершин. | ||
| Строка 124: | Строка 124: | ||
'''Динамические и кинетические остовы''' | '''Динамические и кинетические остовы''' | ||
О динамических или кинетических остовах известно не так уж много. Арья и др. [4] предложили структуру данных размера O(n log n), поддерживающую остов на базе списков с пропусками, описанный выше, с ожидаемым амортизированным временем вставки и удаления <math>O(log^d \; n \; log \; log \; n)</math> на основе модели случайных обновлений. | О динамических или кинетических остовах известно не так уж много. Арья и др. [4] предложили структуру данных размера <math>O(n \; log^d \; n)</math>, поддерживающую остов на базе списков с пропусками, описанный выше, с ожидаемым амортизированным временем вставки и удаления <math>O(log^d \; n \; log \; log \; n)</math> на основе модели случайных обновлений. | ||