Эффективно проверяется, какая из большого набора узлов близка?

Question

В настоящее время я заинтересован в генерации случайных геометрических графов. Для моей конкретной задачи мы произвольно размещаем узел v в единичном квадрате и добавляем ребро от v к узлу u, если они имеют Euclidean distance < = D, где D = D (u, n) изменяется с u и количеством узлов n на графике.

Важные моменты:

• Это дорого для вычисления D, поэтому я хотел бы, чтобы минимизировать количество вызовов этой функции.

• Подавляющее большинство времени, когда добавлено v, грани uv будут добавлены только к небольшому числу узлов u (обычно 0 или 1).

Вопрос: Что представляет собой эффективный метод для проверки, какие вершины у являются «достаточно близко» к V?

Алгоритм грубой силы заключается в вычислении и сравнении dist (v, u) и D (u, n) для всех существующих узлов u. Для этого требуется O (n) звонки D.

Я чувствую, что мы сможем сделать намного лучше этого. Возможно, какой-то битнинг будет работать. Мы могли бы разделить пространство на бункеры, затем для каждой вершины u, мы сохраняем список ящиков, где вновь размещенная вершина v может привести к краю uv. Если v заканчивается помещением вне списка бункеров (что должно происходить в большинстве случаев), то оно слишком далеко, и нам не нужно вычислять D. Это несколько несовместимо, предложение моей головы, и я не знаю, будет ли это работать хорошо (например, накладные расходы при вычислении достаточно близких бункеров, что может быть слишком дорогостоящим), поэтому я получаю обратную связь.

Answer 1

Основываясь на вашем описании проблемы, я бы выбрал в качестве вашей структуры данных R-tree.

Это позволяет очень быстро выполнять поиск путем сужения множества вершин, которые необходимо выполнить против D резко. Однако при вставке наихудшего случая требуется время O (n). К счастью, вы вряд ли попадете в наихудший вариант с типичным набором данных.

Answer 2

Возможно, я бы использовал метод биннинга.

Скажем, мы разрезаем единичный квадрат в m x m подзаголовках (каждый из которых имеет длину стороны 1/m, конечно). Поскольку вы произвольно помещаете свои вершины (или так я предполагал), каждый квадрат будет содержать в среднем n/m^2 вершин.

В зависимости от A1, A2, m и n, вы можете определить максимальный радиус, необходимый для проверки. Скажем, что это меньше, чем m. Затем, после вставки v, вам нужно будет проверить квадрат, в который он приземлился, плюс все смежные квадраты. Во всяком случае, это постоянное число квадратов, поэтому для каждой вставки вам нужно будет проверить в среднем O(n/m^2) других вершин.

Я не знаю, самое лучшее значение для m (как было сказано, что зависит от A1 и A2), но говорят, что это будет sqrt(n), то весь алгоритм может работать в O(n) ожидаемое время.

EDIT Небольшое дополнение: вы можете отслеживать вершины со многими соседями (поэтому с большим радиусом, который распространяется на несколько квадратов) и проверять их для каждой вставленной вершины. Их должно быть мало, так что это не проблема.