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

Bounty

Этот вопрос поднимает несколько проблем. Наградой будет ответ, который рассматривает их в целом.

---

Вот проблема, с которой я играл.

ПРИМЕЧАНИЕ Меня особенно интересуют решения, которые не основаны на евклидовом пространстве.

Существует набор Актеров, которые образуют толпу размером K. Расстояние d (ActorA, ActorB) легко вычислимо для любых двух субъектов (решения должны работать для различных определений «расстояния») и мы можем найти набор из N ближайших соседей для любого данного Актера, используя любой из ряда установленных алгоритмов.

Этот набор соседей верен в первый момент, но Актеры всегда перемещаются , и я хочу для поддержания развивающегося списка N ближайших соседей для каждого Актера. Что меня интересует, так это приблизительные решения, которые более эффективны, чем идеальные решения.

1. Решения должны сходиться к правильным после того, как были внесены ошибки.
2. Иногда допустимо выполнять полное пересчет, если ошибки становятся слишком большими, но обнаружение этих ошибок должно быть дешевым .

До сих пор я использовал алгоритм друга :

recompute_nearest (Actor A)
{
    Actor f_o_f [N*N];
    for each Actor n in A.neighbours
        append n to f_o_f if n != A and n not in f_o_f

    Distance distances [N*N];
    for 0 <= i < f_o_f.size
        distances [i] = distance (A, f_o_f [i])

    sort (f_o_f, distances)
    A .neighbours = first N from f_o_f
}

Это работает достаточно хорошо, когда толпа движется медленно, а N достаточно велико. Он сходится после небольших ошибок, удовлетворяя первым критериям, но

• у меня нет хорошего способа обнаруживать большие ошибки,
• У меня нет количественного описания размера и частоты ошибок,
• он сходится на практике но я не могу доказать , что так будет всегда.

Можете ли вы помочь с любым из этих пунктов?

Кроме того, знаете ли вы какие-либо альтернативные подходы, которые хорошо работают

• , когда толпа быстро движется,
• когда некоторые актеры быстро движутся,
• когда N мало,
• когда толпа в одних местах редкая, а в других густая,
• или с конкретными алгоритмами пространственного индексирования?

Расширение, над которым я работаю в данный момент, - это обобщение функции "друг друга", чтобы взять друга-друга-друга в случаях, когда сосед быстро движется. Я подозреваю, что это плохо масштабируется, и трудно получить правильные параметры без количественной оценки ошибок.

Я приветствую все предложения! Это небольшая забавная проблема: -)

---

Известные предложения на данный момент

Фексвез: выборка случайных дополнительных соседей, размер выборки зависит от скорости агента. Возможно, также поможет отбор проб из области, в которую он собирается переехать.

Повторная выборка соседей, когда агент скорость * delta_time превышает расстояние до самого дальнего известного соседа.

Сохранение триангуляции Делоне , которая является расширенным набором графа ближайших соседей . Учитывает только одного ближайшего соседа.

Библиотека ANN Дэвида Маунта Кажется, не обрабатывает движущиеся тела.