Znajdowanie najbliższej pary między dwoma zestawami punktów na hipersześcianie

Biorąc pod uwagę dwa podzbiory hipersześcianu wymiarowego (tj. ), szukam algorytmu, który pobiera punkty Hammer odległość (lub odległość na hipersześcianie) jest minimalna. Naiwny algorytm sprawdzający tylko każdą parę potrzebuje czas, czy jest jakiś lepszy znany wynik? $d$ $M, N \subseteq \{0,1\}^d$ $m\in M, n\in N$ $L_1$ $d_H(m,n)$ $|M|\cdot |N| \cdot d$

Dla uproszczenia możemy założyć, że . $|M|=|N|=d$

cg.comp-geom HdM
źródło

hmmm. czy jest jeszcze jakaś motywacja / aplikacja? podejrzewam, że istnieje wielowymiarowy analog tego euklidesowego / płaskiego algorytmu, ale wikipedia nic nie cytuje i nie słyszałem o tym gdzie indziej ... może pomóc w poszukiwaniu algorytmu dla wektorów n-dim. początek artykułu wydaje się potwierdzać, że można go rozwiązać w dla wyższych wymiarów ale nie podaje żadnego cytatu. może gdzieś w referencjach?

O (n \log n)

$O(n \log n)$

d > 2

$d>2$

vzn

Argument dziel i zwyciężaj opiera się na ograniczeniu pakowania. W wyższych wymiarach wprowadza to współczynnik w nawrocie, ale zależność od pozostaje taka sama. Więc jeśli nie masz nic przeciwko terminom wykładniczym w , możesz użyć tego podejścia. Jeśli chcesz czegoś dokładnego, prawdopodobnie nie będziesz w stanie zrobić nic lepszego.

2^{d}

$2^d$

n

$n$

d

$d$

Suresh Venkat

patrz także wyszukiwanie najbliższego sąsiada

vzn

Wydaje się to mało prawdopodobne. Pomyśl o n + m losowych ciągów w hipersześcianie. Jakoś odległość uderzenia każdej pary wynosi w przybliżeniu d / 2 i musisz sprawdzić wszystkie pary, aby znaleźć najbliższą parę.

Sariel Har-Peled

@Sariel Har-Peled: Jak napisał Suresh, problem można rozwiązać w czasie O (n log n) (gdzie n = max {| M |, | N |}) dla dowolnej stałej d. Dlatego „musisz sprawdzić wszystkie pary, aby znaleźć najbliższą parę”, nie brzmi to dla mnie poprawnie.

Tsuyoshi Ito

Odpowiedzi:

$|M|=|N|=d$ $M$ $X$ $N$ $Y$ $Y$ $Z=XY$ $z_{i,j}$ $i$ $M$ $j$ $N$ $O(d^{2.3727})$ $O(d^{2.3726999999})$

Podobny efekt można uzyskać, jeśli macierze nie są kwadratami. Myślę, że w tym przypadku Uri Zwick ma artykuł na temat szybkiego mnożenia macierzy.

$O(|M| * |N|)$ $d$

Sariel Har-Peled
źródło

Świetne znalezisko. Na innej notatce mój kolega znalazł ten artykuł: toc.cse.iitk.ac.in/articles/v008a014/v008a014.pdf i dopiero teraz zdaję sobie sprawę, że został (również) napisany przez ciebie. Strona 17+ jest szczególnie interesująca ..

HdM

Tak. Wygląda znajomo - zauważ jednak, że jest to przybliżenie - Suresh poprosił o dokładny wynik ...

Sariel Har-Peled

-3

$L_\infty$ $L_m$ $L_1$ $O(dn \log n)$ $d$

[1] Optymalny algorytm wyszukiwania przybliżonego najbliższego sąsiada w ustalonych wymiarach Arya i in., 30pp

[2] Efektywni najbliżsi sąsiedzi szukający hipersześcianu, z zastosowaniami do grupowania molekularnego Cazals

vzn
źródło

Ω (d^{d})

$\Omega(d^d)$