Нахождение ближайшей пары между двумя наборами точек на гиперкубе

11

Для двух подмножеств мерного гиперкуба (т. Е. M , N { 0 , 1 } d ) я ищу алгоритм, который извлекает точки m M , n N на расстоянии Хэмминга (или L 1 - расстояние по гиперкубу) d H ( m , n ) минимально. Наивный алгоритм, который проверяет только каждую пару | М | | N | дdM,N{0,1}dmM,nNL1dH(m,n)|M||N|d время, есть ли лучший результат известен?

Для простоты можно предположить, что .|M|=|N|=d

HDM
источник
хммм. есть ли еще мотивация / приложение? Подозреваю, что существует многомерный аналог этого евклидова / планарного алгоритма, но википедия ничего не цитирует и не слышала об этом где-либо еще ... это может помочь найти алгоритм для n-dim векторов. начало статьи, кажется, утверждает, что она может быть решена в для более высоких измерений d > 2, но не дает цитирования. может где то в ссылках? O(nlogn)d>2
ВЗН
1
Аргумент «разделяй и властвуй» опирается на границу упаковки. В более высоких измерениях, это вводит фактора в рецидиве, но зависимость от п остается тем же самым . Так что, если вы не возражаете против экспоненциальных терминов в d , вы можете использовать этот подход. Если вы хотите что-то точное, вы вряд ли сможете добиться большего. 2dnd
Суреш Венкат
1
Это кажется маловероятным. Подумайте о n + m случайных строк в гиперкубе. Так или иначе, расстояние Хэмминга каждой пары примерно равно d / 2, и вам нужно проверить все пары, чтобы найти ближайшую пару.
Сариэль Хар-Пелед
@Sariel Har-Peled: Как писал Суреш, эту проблему можно решить за время O (n log n) (где n = max {| M |, | N |}) для любой константы d. Поэтому «вы должны проверить все пары, чтобы найти ближайшую пару», мне не кажется правильным.
Tsuyoshi Ito

Ответы:

6

|M|=|N|=dMXNYYZ=XYzi,jiMjNO(d2.3727)O(d2.3726999999)

Вы можете получить аналогичный эффект, если матрицы не квадратные. Я думаю, что у Ури Цвика есть статья о быстром умножении матриц в этом случае.

O(|M||N|)d

Сариэль Хар-Пелед
источник
Отличная находка. С другой стороны, мой коллега нашел этот документ: toc.cse.iitk.ac.in/articles/v008a014/v008a014.pdf, и только теперь я понимаю, что он (также) был написан вами. Страница 17+ особенно интересна ..
HdM
Да. Выглядит знакомо - но обратите внимание, что это приблизительное значение, - Суреш спросил точный результат ...
Сариэль Хар-Пелед