Эффективная структура данных для ближайшего евклидова расстояния

Question

Этот вопрос вызван следующей проблемой UVa: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=18&page=show_problem&problem=1628.

Для мониторинга климата в регионе Амазонки была установлена сеть автономных станций сбора данных, работающих на батарейках.Станция отправки заказов может инициировать передачу инструкций на станции управления, чтобы они изменили свои текущие параметры.Чтобы избежать перегрузки аккумулятора, каждая станция (включая станцию отправки заказов) может передавать данные только на две другие станции.Конечными пунктами станции являются две ближайшие станции.В случае ничьей первым критерием является выбор самого западного (крайнего левого на карте), а вторым критерием является выбор самого южного (самого низкого на карте).Правительство штата Amazon поручило вам написать программу, которая решает, могут ли сообщения, учитывая локализацию каждой станции, доходить до всех станций.

Наивный алгоритм, конечно, построил бы граф со станциями в качестве вершин и вычислил бы ребра из данной вершины путем поиска по всем другим вершинам ближайших двух.Тогда мы могли бы просто запустить DFS / BFS.Конечно, для этого требуется $O(V^2)$ время для построения графика (который действительно проходит тестовые примеры).Однако мой вопрос заключается в том, можем ли мы построить график еще быстрее с соответствующей структурой данных.В частности, учитывая произвольную точку запроса $p$ и заданный набор точек $S$, можем ли мы организовать точки в $S$ таким образом, мы можем быстро найти две ближайшие точки в $S$ Для $p$ (скажем, в $\log V$ время?).

Answer 1

Если я правильно понимаю, можно было бы использовать большинство пространственных индексов.

Пространственные индексы обычно имеют около $O(log{V})$ время вставки и аналогичное время поиска для ближайших соседей.Конечно, вы можете создать диаграмму Вороного на основе этого, но вы также можете использовать индекс напрямую, чтобы находить ближайших соседей всякий раз, когда они вам понадобятся.

Для низкой размерности (2D, 3D) общими семействами пространственных индексов являются kd-деревья (довольно простой и в целом хороший, но, как правило, возникают проблемы с плотными скоплениями точек), квадродеревья (немного сложнее реализовать самостоятельно, потому что числовая точность может быть сложной) и R-Дерево (сложнее всего реализовать, но дает наилучшую гарантированную производительность, особенно R *Tree (R-Star-Tree)).

Если вы используете C ++, взгляните на libSpatialIndex - Индекс библиотеки или тот Увеличить R-дерево.Если вы используете Java, взгляните на мой Жестяная прядильня библиотека.

Технический термин для этого - "$k$ запросы ближайшего соседа " или "$k$-NN запросов", с $k$ имеется в виду количество ближайших соседей, которых вы хотите найти.

Answer 2

Похоже, что соответствующая структура данных может быть динамической Диаграмма Вороного.

Диаграммы Вороного часто являются ответом, когда речь идет о наборе точек на плоскости.

В этом случае, поскольку набор точек развивается, вам нужна динамическая версия.