Как эффективно найти самую дальнюю точку (из набора точек) из данной точки?

Question

Я ищу алгоритм или структуру данных для решения следующей проблемы: Вам дан набор баллов S. И вам задают Q запросов в виде другой точки. Для каждого запроса найдите самую дальнюю точку в наборе из заданной точки.

В наборе не более 10 ^ 5 точек и 10 ^ 5 запросов. Все координаты для точек находятся в диапазоне от 0 до 10 ^ 5.

Мне интересно, есть ли способ сохранить набор точек, чтобы мы могли отвечать на запросы в O (log n) или O (log ^ 2 n), если это необходимо.

Answer 1

Цитата из «Приблизительный самый дальний сосед с заявкой» к кольцевому запросу ":

В двух измерениях проблема дальнего соседа может быть решена в линейном пространстве и логарифмическом времени запроса, используя местоположение точки в самая дальняя точка диаграммы Вороного (см., например, де Берг и др. [5]).

, где [5] относится к «Учебнику по меткам»:

Берг, Марк де, Отфрид Чонг, Марк ван Кревельд и Марк Овермарс. Вычислительная геометрия: алгоритмы и приложения . Springer-Verlag TELOS, 2008.

<ч />
^{Диаграмма дальнего соседа Вороного для набора из восьми точек.
Изображение от Jacometti, Welson. «Записка о примитивах для манипулирования общими подразделениями и вычисления диаграмм Вороного». (1992).}

<ч />