Как найти уникальный набор ближайших пар точек в 1D?

Мой вопрос очень похож на этот: Как найти уникальный набор ближайших пар точек?

Единственная разница в том, что я в 1D.

Итак, у меня есть два набора точек (поскольку я нахожусь в 1D, мы можем видеть их как числа от 0 до 1) A и B, каждый из которых содержит m и n элементов соответственно, с m ‹= n

Моя цель - найти набор C, состоящий из m РАЗЛИЧНЫХ точек в B, которые минимизируют сумму расстояний [A (i), C (i)] Если m = n, я могу использовать расстояние Вассерштейна, которое имеет красивую одномерную реализацию. В 2D я бы использовал венгерский алгоритм, но это довольно дорого, и я надеюсь, что в 1D есть более быстрое решение.

Спасибо


algorithm geometry closest
person Adrien Nivaggioli    schedule 10.06.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Мысли вслух:

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

Стоимость этого процесса составляет O (NA Log NA) + O (NB Log NB) + O (NA + NB), где последний член может быть поглощен.

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

Пока все хорошо, но, к сожалению, ближайший сосед также может быть ближайшим к соседней точке в A, и конфликт необходимо разрешить (одна из точек A должна быть назначена другому B-соседу). В худшем случае это может вызвать каскадные конфликты.

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

введите описание изображения здесь

person Yves Daoust    schedule 10.06.2020
comment
Спасибо за ваш ответ. В лучшем случае он кажется лучше, чем венгерский алгоритм, но в худшем - худший, поскольку время выполнения вашего решения становится экспоненциальным. Я правильно понял? - person Adrien Nivaggioli; 10.06.2020
comment
@AdrienNivaggioli: поскольку венгерский алгоритм имеет полиномиальное время, а мой подход - экспоненциальный наихудший случай, последний не следует использовать вообще. Я предполагаю, что лучшее решение может быть получено путем тщательного изучения венгерского алгоритма, чтобы проверить, можно ли с помощью трюка сортировки снизить сложность. В настоящее время я недостаточно разбираюсь в этом алгоритме, чтобы помочь. - person Yves Daoust; 10.06.2020
comment
Спасибо ! Если я найду лучшее решение, я вернусь, чтобы опубликовать его здесь! - person Adrien Nivaggioli; 10.06.2020