Задача о ближайшей паре точек
-
Задача о ближайшей паре точек
- Задача о нахождении пары точек с наименьшим расстоянием в метрическом пространстве.
- Рандомизированные алгоритмы решают задачу за линейное время, в отличие от наивного алгоритма с
- O
- (
- n
- 2
- )
- временем.
- Без рандомизации возможно решение с использованием машинных моделей с произвольным доступом и памятью, что позволяет использовать функцию пола.
-
Линейные рандомизированные алгоритмы
- Алгоритм Рабина (1976) с модификацией Липтона для упрощения анализа.
- Равномерная выборка пар точек упрощает доказательство линейности ожидаемого числа расстояний.
- Алгоритм Khuller & Matias (1995) использует итерационный процесс фильтрации для приближения ближайшего расстояния.
-
Динамическая задача о ближайшей паре
- Алгоритмы и структуры данных для пересчета ближайшей пары при вставке или удалении объектов.
- Пространственная структура данных с ожидаемым
- бревно
-
- временем вставки и удаления и постоянным временем запросов.
- Сложность алгоритма в трехмерном пространстве экспоненциальна в измерении расстояния, что делает его менее подходящим для больших размерностей.
-
Ссылки
- ГИС
- Поиск ближайшего соседа
- Записи