Лучший способ отслеживать максимальное расстояние в наборе точек?

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

Ответы

Ответ 1

Теоретически, вы можете сделать это эффективно, сохранив выпуклый корпус ваших очков.

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

Аналогично, если вы удаляете точку изнутри, максимальное расстояние (диаметр) сохраняется, поэтому ничего не меняйте. Однако, если вы удаляете граничную точку, тогда выпуклая оболочка должна быть пересчитана.

Если вы находитесь в двух измерениях, то при добавлении или удалении с границы затронуты не более двух сторон полигона. Их можно легко вычислить, в зависимости от того, как вы храните информацию (например, последовательность сегментов линии).

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

Ответ 2

Вместо использования выпуклой оболочки (как предлагается в другом ответе) вы можете использовать триангуляцию Делоне??

Минимальное расстояние:

Чтобы вычислить минимальное расстояние от a node до любого другого в наборе, вам нужно только проверить непосредственные соседи node, то есть те, которые связаны с ним краем в триангуляции.

Итак, если вставлен новый node, обновите триангуляцию, найдите соседей нового node и любых других узлов, которые были "вовлечены" в обновление, вычислите расстояния для всех узлов в этом локальном "обновленном" "установите и проверьте, был ли найден новый минимум. Аналогично, если существующий node удален, снова обновите триангуляцию и пересчитайте расстояния для всех задействованных узлов.

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

Максимальное расстояние:

Как было предложено в ответе стиля выпуклой оболочки, вам нужно будет только пересчитать расстояния между граничными узлами, если новый node был добавлен за пределы существующей триангуляции или если была удалена существующая граница node.

Надеюсь, что это поможет.

Ответ 3

Я не уверен, что это лучше всего, но это лучшее, что я могу сейчас придумать.

Сохраните макс вместе с набором пар точек на этом расстоянии. (Макс не обязательно уникален.)

То же самое и для мин.

  • Когда вы добавляете точку, вычисляете новое расстояние точки до всех остальных точек и заменяете сохраненные max и min вместе с соответствующим набором пар конечных точек, если новая точка участвует в лучшем макс или мин или обновите набор конечных точек, если он соответствует текущему лучшему.

  • Когда вы удаляете точку, убедитесь, что она очищает целую запомненную минимальную или максимальную точку включения. Если нет, вам ничего не нужно. Но если это так, я думаю, вам нужно будет перепроверить все.

Для максимального вычисления, я считаю, что предложение PengOne может рассказать вам, можете ли вы полностью пропустить вычисление.