Najbliższa para punktów między dwoma zestawami, w 2D

Mam dwa zestawy punktów w płaszczyźnie dwuwymiarowej. Chcę znaleźć najbliższą parę punktów taką, że , , a odległość euklidesowa między jest tak mała, jak to możliwe. Jak skutecznie można to zrobić? Czy można tego dokonać w czasie , gdzie ? $S,T$ $s,t$ $s \in S$ $t \in T$ $s,t$ $O(n \log n)$ $n = |S|+|T|$

Wiem, że jeśli mam podane jednolity zbiór , to jest możliwe, aby znaleźć najbliższą parę punktów w czasu przy użyciu standardowego algorytmu dziel i zwyciężaj . Jednak algorytm ten nie wydaje się uogólniać na przypadek dwóch zestawów, ponieważ nie ma związku między odległością między dwoma najbliższymi punktami w obrębie lub a odległością między dwoma najbliższymi punktami w tych zestawach. $S$ $s,s' \in S$ $O(n \log n)$ $S$ $T$

Myślałem o zapisaniu zbioru w drzewie -d, a następnie dla każdego , używając zapytania najbliższego sąsiada, aby znaleźć najbliższy punkt w do . Jednak najgorszy możliwy czas działania może być tak zły, jak czas . Istnieją wyniki mówiące, że jeśli punkty są losowo rozmieszczone, to oczekiwany czas działania dla każdego zapytania wynosi , więc uzyskalibyśmy algorytm o oczekiwanym czasie działania $T$ $k$ $s \in S$ $T$ $s$ $O(n^2)$ $T$ $O(\log n)$ $O(n \log n)$ gdybyśmy mieli gwarancję, że punkty są losowo rozmieszczone - ale szukam algorytmu, który będzie działał dla dowolnej kolekcji punktów (niekoniecznie losowo rozmieszczonych).

Motywacja: wydajny algorytm byłby przydatny w przypadku tego drugiego pytania .

algorithms computational-geometry

— DW
źródło

Odpowiedzi:

Tak, może to być czas . Budowanie diagramu Voronoi dla . Następnie dla każdego punktu znajdź, w której komórce diagramu Voronoi jest zawarty. Środek tej komórki to punkt najbliższy . $O(n \log n)$ $T$ $s \in S$ $t \in T$ $s$

Możesz zbudować diagram Voronoi w czasie , a każde zapytanie (znajdź komórkę zawierającą ) można wykonać w czasie , więc całkowity czas działania to czas . $O(n \log n)$ $s$ $O(\log n)$ $O(n \log n)$

— DW
źródło

Fajne, znacznie prostsze niż to, co mogłem wymyślić :).

— aelguindy,

Niezłe podejście! Pomocne byłyby jednak linki, szczególnie po stronie zapytań. Mógłbym znaleźć stronę Wikipedii pokazującą, że ogólny problem lokalizacji punktu można rozwiązać w czasie

, ale czy istnieje lepszy sposób na specjalny przypadek komórek Voronoi? Moje wyszukiwanie ujawniło tylko tę odpowiedź , co czyni ją

O (\log n)

$O(\log n)$

O (n)

$O(n)$

— j_random_hacker

T

$T$

n = | S | + | T |

$n = |S| + |T|$

O (n)

$\mathcal{O}(n)$

n

$n$

O (n)

$O(n)$

\leq 6 n

$\le 6n$

To wydaje się poprawne w przypadku tego pytania na temat wymiany matematyki.

— Albjenow

$L^1$

$d$ $O(n \log^{d-1} n)$

$O(n \log n)$ $O(n \log^2 n)$

$S, T$ $S$ $-\delta_z$ $T$ $\delta_z$ $z$ $\delta_z$ $\delta_z$

— aelguindy
źródło

P_{2}

$P_2$

p_{m}

$p_m$

P

$P$ $P$

q_{m}

$q_m$

Q

$Q$ $Q$

l

$l$

Link jest zepsuty :(

— Keerthana Gopalakrishnan