3622
правки
Изменения
Нет описания правки
#:* Неплохо бы для понимания добавить картинки из гуглящейся презентации
#:* Добавить категории
# [[Ортогональный поиск]]
## Впихнуть в Range tree (берётся вместе со следующим конспектом)
# [[Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)]] (''20'')
## Написать в одномерном случае сначала, что его можно решать проще, а в двумерном, что можно использовать простой вариант одномерного в узле
# [[Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (log^2 на добавление/удаление)]]
# [[Выпуклая оболочка в n-мерном пространстве]]
# [[Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]]
# [[Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой]]
# [[Пересечение полуплоскостей, связь с выпуклыми оболочками]]
# [[Алгоритм Бентли-Оттмана]]
# [[Пересечение множества отрезков | Пересечение множества отрезков ]] (''15'')## Помёрджить с конспектом про Бентли-Оттмана## Написать понятный конспект с описанием всех шагов и частных случаев# [[Алгоритм Балабана]] <tex>^\star</tex># [[Конфигурация]]# [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых]]# [[Пересечение многоугольников (PSLG overlaying)]]# [[Локализация в ППЛГ методом полос (персистентные деревья) | Локализация в ППЛГ методом полос (персистентные деревья)]]# [[Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]]
# [[Трапецоидная карта]]
# [[Упрощение полигональной цепи]]
# [[BSP-дерево]]
== Скалярное произведение и мера (проверяется) ==
