Учитывая n точек в 2-D плоскости, мы должны найти k ближайших соседей каждой точки между собой

#algorithm #data-structures #geometry #nearest-neighbor

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

Вопрос:

Я исследовал метод с использованием минимальной кучи. Для каждой точки мы можем хранить минимальную кучу размером k, но для больших n требуется слишком много места (я нацеливаюсь на n около 100 миллионов).). Конечно, должен быть лучший способ сделать это, используя меньшее пространство и не сильно влияя на временную сложность. Существует ли какая-либо другая структура данных?

1. Насколько большое значение n влияет на «много места» — размер кучи равен k ? Вы рассматривали en.wikipedia.org/wiki/K-d_tree для вас размер набора данных?

2. Я думаю, что meta рассматривает один minheap для каждой точки. Таким образом, будет общая n минимальная куча с размером k , что займет n*k всего места.

3. @SauravSahu Да, я думал об этом именно так.

Ответ №1:

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

Альтернативным подходом может быть использование bucketing для уменьшения сложности наивного алгоритма. Идея состоит в том, чтобы разделить плоскость на «сегменты», то есть квадраты определенного размера, и поместить точки в сегмент, к которому они принадлежат. Ближайшие точки будут из ближайших сегментов. В случае случайных данных это может быть неплохим улучшением, но наихудший случай остается таким же, как и при наивном подходе.

1. Я узнаю о KD-дереве. Также подход bucketing кажется довольно хорошим. Какая структура данных, по вашему мнению, будет подходящей для ее реализации? Я думаю, что поиск по ширине в графе с ребрами, представляющими смежность между сегментами (узлами) в двумерной плоскости, был бы неплохим.

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