Сортировка по евклидовому расстоянию

- это множество точек на плоскости. Случайная точка задается на той же плоскости. Задача состоит в том, чтобы отсортировать все по евклидову расстоянию между и . $S$ $x \notin S$ $y \in S$ $x$ $y$

Бездумный подход состоит в том, чтобы вычислить расстояния между и для всех а затем отсортировать их, используя любой быстрый алгоритм. $x$ $y$ $y \in S$

Есть ли способ сохранить или предварительно обработать чтобы процесс сортировки стал быстрее? $S$

cg.comp-geom sorting Алекс К.
источник

Вы можете рассмотреть сетку соответствующего размера и групповые точки по соответствующему квадрату (используя, скажем, хэш-таблицу). Тогда для определенных пар квадратов вы можете сделать вывод, что все точки одного квадрата находятся дальше от

чем все точки другого квадрата. На практике это может помочь, я думаю.

x

$x$

Ильяраз

«Безмозглый подход», который вы заявили, работает за время O (n log n), где n - это количество точек в S, которое, как мне кажется, довольно быстрое на практике. Вы хотите исключить коэффициент логарифмирования или что-то еще, например внешнюю сортировку ?

Tsuyoshi Ito

Дело в том, что у меня есть практически неограниченное время для подготовки набора баллов, но время для их сортировки очень ограничено. Тем не менее, приветствуется любое ускорение стандартной сортировки - даже если оно такое же O (n log n), но быстрее в худшем случае (или в лучшем случае, или как угодно).

Алекс К.

Например, если я храню S как двумерное дерево, я могу найти одного ближайшего соседа за O (log n). Может быть, есть аналогичное решение для моей задачи. Я не большой специалист по структурам пространственных данных - а их так много - я мог бы легко пропустить это.

Алекс К.

Ответы:

Решение 1. Найдите перпендикулярные биссектрисы между парами точек и постройте расположение этих прямых. Компоновка имеет ячеек, в которых отсортированный порядок постоянен. Поэтому создайте структуру данных местоположения точек для расположения и украсьте каждую ячейку отсортированным порядком, который должен быть возвращен для точек в этой ячейке. Сортированные порядки между соседними ячейками различаются только в одном транспонировании, поэтому вы можете использовать постоянную структуру данных, чтобы представления этих отсортированных порядков могли совместно использовать пространство. Общее пространство и время запроса $\Theta(n^2)$ $\Theta(n^4)$ $O(n^4)$ . $O(\log n)$

Решение 2: Выберите случайную выборку из этих же перпендикулярных биссектрис, построите их расположение и разделите каждую ячейку расположения вертикальными отрезками, проходящими через каждое пересечение двух выбранных линий. Результирующее разбиение имеет ячеек, каждая из которых с высокой вероятностью пересекается несэмплированными биссектрисами. Украсьте каждую ячейку раздела с помощью правильного отсортированного порядка точек, если смотреть с некоторого x внутри ячейки. Общее пространство . $\Theta(n)$ $\Theta(n^2)$ $O(n)$ $O(n^3)$

Теперь, чтобы выполнить запрос, найдите точку запроса в разделе, найдите порядок, сохраненный в ячейке раздела, и используйте алгоритм сортировки сравнения декартовых деревьев Levcopoulos & Petersson (1989), начиная с этого сохраненного порядка. Время для этого шага пропорционально где - количество точек, которые не соответствуют порядку точки . Но это (каждая биссекторные причины без выборки не более одного испорченных паров точек), поэтому во время запроса $\sum_i O(1+\log k_i)$ $k_i$ $y_i$ $\sum k_i$ $O(n)$ также является . $\sum_i O(1+\log k_i)$ $O(n)$

Дэвид Эппштейн
источник

PS вот альтернативный вариант решения 2, который использует то же пространство и время запроса, но заменяет

Дэвид Эппштейн

Зачем выполнять предварительную обработку

когда можно отсортировать по всем

начальным точкам за

времени и сохранить результаты в хеш-таблице, используя пространство

для постоянного поиска?

n^{4}

$n^4$

n

$n$

O (n^{2} \log n)

$O(n^2\log n)$

O (n^{2})

$O(n^2)$

Дейв

Потому что есть

начальных точек с разными порядками сортировки, а не

Θ (n^{4})

$\Theta(n^4)$

Θ (n^{2})

$\Theta(n^2)$

Дэвид Эппштейн

Вы, вероятно, не сможете уйти от времени, как бы вы его ни разрезали; даже предварительные вычисления областей, соответствующих всем возможным порядкам сортировки, могут (я считаю) привести к областям, и, таким образом, нахождение «вашей» области с помощью любого значимого метода поиска примет время. ( РЕДАКТИРОВАТЬ: $n\log(n)$ $O(n!)$ $O(\log(n!)) = O(n\log(n))$ это абсолютно неправильно; см. отличный ответ Дэвида Эппштейна для получения дополнительной информации!) С другой стороны, один полезный способ снизить сложность - особенно, если вам не нужна полная сортировка сразу, а просто нужно иметь возможность случайным образом выбрать й ближайший на лету - может быть с помощью диаграмм Вороного высшего порядка: расширения стандартной ячейки Вороного, в которых размещается не только ближайший сосед, но и второй ближайший, и т. д. Статья Фрэнка Дине о поиске k-ближайшего соседа, http: //people.scs .carleton.ca / ~ dehne / публикации / 2-02.pdf представляется канонической ссылкой; На его домашней странице http://www.dehne.carleton.ca/publications есть ряд других статей о диаграммах Вороного, которые могут быть полезны. $k$

Стивен Стадницки
источник

Если разделить плоскость на области с разными порядками сортировки, существует

областей, а не

. Границами между областями являются перпендикулярные биссектрисы линий пар точек, таких линий

, а набор областей задается расположением этих линий.

Θ (n^{4})

$\Theta(n^4)$

O (n!)

$O(n!)$

Θ (n^{2})

$\Theta(n^2)$

Дэвид Эппштейн

@ Дэвид, я думаю, ты должен ответить на этот вопрос.

Джеймс Кинг,

Вторую - п! чувствовал себя неправильно, когда я писал это, но я не мог видеть дело против. Я исправлю свой ответ в ближайшее время, чтобы исправить это, но я действительно хотел бы видеть более прямо информированный; Спасибо!

Стивен Стадницки