Конспект: локализация, kd-дерево и диаграмма Вороного

Понятия

Локализация точки - по разбиению плоскости и точке назвать область; ответ - отрезок прямо под точкой.

Полоса - часть плоскости между соседними вертикалями через концы отрезков; внутри неё отрезки не кончаются и упорядочены по высоте.

Трапецоидная карта - разбиение на трапеции вертикалями из концов до ближайших отрезков; с графом поиска при случайном порядке вставки.

kd-дерево - разрезы медианой по координатам по очереди. Проклятие размерности - в больших размерностях отсечение перестаёт работать.

Диаграмма Вороного - ячейки ближайших точек. Береговая линия - нижняя огибающая парабол пройденных центров в алгоритме Форчуна.

Что унести

ЛОКАЛИЗАЦИЯ
полосы (Добкин, Липтон, 1976): запрос - два двоичных поиска, O(log n)
    память до O(n²): лестница из 60 отрезков - 1860 записей
    сравнение в полосе - в середине полосы, в целых
трапецоидная карта (Сейдел 1991, Малмулей 1990), случайный порядок:
    ожидаемо O(n) памяти (трапеций <= 3n + 1), O(log n) на запрос,
    O(n log n) на построение
граница полос - договор: полуоткрытые полосы, иначе споры на вертикали

kd-ДЕРЕВО
узел: медиана по оси, ось по кругу; глубина log n
поиск: ближнее поддерево, потом дальнее, если
       (q[ось] − p[ось])² < лучшее   (для ничьих - <=)
600 точек на плоскости: 14 узлов на запрос, все 40 верны
300 точек: d = 2 - 4% узлов, d = 4 - 12%, d = 8 - 67%
большая размерность: LSH, графы близости (HNSW)
scipy.spatial.KDTree / cKDTree; в PostGIS - оператор <->

ДИАГРАММА ВОРОНОГО
ячейка = пересечение полуплоскостей серединных перпендикуляров
вершина = центр пустой окружности через 3 центра
ребро = равноудалено от 2 центров при пустой окружности
бесконечна ячейка центра на границе выпуклой оболочки
V <= 2n − 5, E <= 3n − 6; в общем положении V = 2n − 2 − h
    12 центров, h = 5: 17 вершин
пустота окружности - определитель 3 × 3 в целых
    (тот же предикат - в следующей главе)
«кто ближе» = локализация точки в диаграмме, O(log n)

АЛГОРИТМ ФОРЧУНА (1987)                       O(n · log n)
прямая сверху вниз, статус - береговая линия
парабола центра p при прямой y = l:
    y = ((x − px)² + py² − l²) / (2 (py − l))
над береговой линией всё окончательно; изломы чертят рёбра
событие «центр»: дуга X → X Y X, дуг <= 2n − 1
событие «окружность»: нижняя точка пустой окружности через три
    соседние дуги, средняя исчезает, рождается вершина
    A, D, C из урока: центр (11,444; 7,111), событие на высоте 0,289
ложные тревоги удалять из очереди

Ловушки джокера

Запрос на вертикали полосы. Отрезок, начавшийся ровно в x запроса, то входит в полосу, то нет.

Фиксированный порядок вставки в трапецоидную карту. Найдётся вход, где граф поиска - цепочка.

Отсечение kd-дерева по точке узла, а не по прямой. Ближайший прячется у границы.

Строгое неравенство в отсечении при правиле ничьих. Отделение с меньшим номером на границе теряется.

kd-дерево для векторов из сотен признаков. Это перебор с накладными расходами.

Зоны по растру вместо диаграммы. Грубо или огромно.

События-окружности для несоседних дуг и без отмены. Ложные вершины внутри чужих ячеек.

Проверь себя

Почему для локализации хватает отрезка под точкой? Откуда квадратичная память у полос и как её чинит трапецоидная карта? Почему отсечение в kd-дереве верно и почему в восьмимерии оно почти не работает? Почему ячейка Вороного выпукла, что такое её вершина и почему вершин не больше 2n − 5? Что окончательно над береговой линией и когда наступает событие-окружность?

• Дальняя диаграмма Вороного выбирает максимум расстояния; непустые двумерные ячейки принадлежат вершинам оболочки. Для охватывающего круга нужен двухточечный случай, для кольца ещё и ближайшая диаграмма.