Поиск ближайших точек.

1. Формулировки задач.
1. Задача: даны N точек, найти пару ближайших
2. Задача: для каждой из N точек найти ближайшую среди тех же N.
3. Задача: для каждой из N точек найти ближайшую среди множества из других M точек.
2. Диаграмма Вороного
1. Линейный размер (следствие из теоремы Эйлера, и того, что степень каждой вершины > 3)
2. Построение за O(N²) (простой алгоритм, из всех известных мне, самый короткий)
3. Построение за O(NlogN) ScanLine-ом с параболами (не забудем повернуть на случайный угол)
3. Триангуляция Де Лоне
1. Двойственность этих задач (срединный перпендикуляр соединяет два центра описанных окружностей)
2. Построение: итеративный метод с док-вом (если что-то не так, развернем диагональ)
4. Метод проецирования на прямую.
1. Прямая должна быть случайной.
2. Задача 2: тест, на котором работает O(NsqrtN)
3. Задача 3: тест, на котором работает O(N²)
5. Квадродеревья.
1. Собственно подход, схожесть с проекцией на прямую.
2. Задача 2: тест, на котором работает O(NsqrtN)
3. Задача 3: тест, на котором работает O(N²)

Практика

1. Спроецируем на прямую, дубль #1 110304a1 : 1A
2. Спроецируем на прямую, дубль #2 110304a1 : 1B
3. Спроецируем на прямую, дубль #3 110304a1 : 1C
4. Диаграмма Вороного за O(N²) 110304a1 : 1D
5. Диаграмма Вороного за O(NlogN) 110304a1 : 1E
6. Применение ScanLine-а к Диаграмме Вороного за O(NlogN) timus : 1369