Najkrótsza odległość między punktem A i punktem B

Biorąc pod uwagę dwa zestawy i każdy zawierający rozłącznych punktów na płaszczyźnie, oblicz najkrótszą odległość między punktem w a punktem w , tj. .$A$$B$$n$$A$$B$$\min \space \{\mbox{ } \text{dist}(p, q) \mbox{ } | \mbox{ } p \in A \land q \in B \space \}$

Nie jestem pewien, czy mam rację, ale ten problem jest bardzo podobny do problemów, które można rozwiązać za pomocą programowania liniowego w geometrii obliczeniowej. Jednak redukcja do LP nie jest prosta. Również mój problem wygląda na znalezienie najcieńszego punktu między dwoma zestawami punktów, które oczywiście można rozwiązać za pomocą LP w $O(n)$ w przestrzeni dwuwymiarowej.

Mam rozwiązanie, które może wydawać się nieco skomplikowane, ale powinno być bardziej wydajne niż naiwne wyszukiwanie :$\mathcal O(n^2)$

1. niech być oś pomiędzy środkami ciężkości i .$v$$A$$B$
2. Posortuj punkty i wzdłuż tej osi odpowiednio w porządku malejącym i rosnącym, uzyskując sekwencje , , ..., i , , ..., .$A$$B$$a_0$$a_1$$a_n$$b_0$$b_1$$b_n$

Reszta jest w pseudo-kodzie, aby było jaśniej:

d = infinity.
for j from 1 to n
    if (b_1 - a_j) along v > d then break endif
    for k from 1 to n
        if (b_k - a_j) along v > d then
            break
        else
            d = min( d , ||b_k - a_j|| )
        endif
    enddo
enddo

To znaczy, wstępnie sortując punkty wzdłuż , możesz odfiltrować pary, które nigdy nie będą w odległości od siebie, ponieważ wzdłuż zawsze będzie.$v$$d$$b_k-a_j$$v$$\le \|b_k-a_j\|$

W najgorszym przypadku jest to nadal , ale jeśli i są dobrze oddzielone, powinno być znacznie szybsze, ale nie lepsze niż , co jest wymagane do sortowania.$\mathcal O(n^2)$$A$$B$$\mathcal O(n\log n)$

Aktualizacja

To rozwiązanie w żadnym wypadku nie jest wyciągane z kapelusza. Jest to szczególny przypadek tego, czego używam w symulacjach cząstek, aby znaleźć wszystkie oddziałujące pary cząstek z przestrzennym binowaniem. Moja własna praca wyjaśniająca bardziej ogólny problem jest tutaj .

Jeśli chodzi o sugestię użycia zmodyfikowanego algorytmu przesuwania linii, chociaż intuicyjnie prosty, nie jestem przekonany, że jest to w gdy rozważane są zestawy rozłączne. To samo dotyczy losowego algorytmu Rabina.$\mathcal O(n\log n)$

Wydaje się, że nie ma zbyt wiele literatury dotyczącej problemu najbliższych par w rozłącznych zestawach, ale znalazłem to , co nie rości sobie prawa do bycia pod , i to , co nie wydaje się zgłaszać jakiekolwiek roszczenia.$\mathcal O(n^2)$

Powyższy algorytm może być postrzegany jako wariant przemiatania płaszczyzny zaproponowany w pierwszym artykule (Shan, Zhang i Salzberg), ale zamiast używać osi i braku sortowania, oś między zestawami jest używana, a zestawy są trawersowane w porządku malejącym / rosnącym.$x$

Możesz dostosować algorytm „linii najbliższej pary” , którym jest .$O(n \log n)$

Jedyne, co musisz zrobić, to zignorować pary należące do tego samego zestawu.

Edycja: W rzeczywistości nie jest to proste (ani nawet możliwe), jak opisałem. Zobacz komentarze do dyskusji.

Ideą w takich problemach jest stworzenie uporządkowanej struktury z jednego z zestawów, który umożliwia wydajne zapytania Najbliższego sąsiada. Klasyczny artykuł, który przedstawiał strukturę zapytań O (log n) dla dowolnego wymiaru, brzmiał:

Shamos i Hoey o rozwiązaniach Voronoi

Od tego czasu powstało wiele innych partycji kosmicznych opartych na pomysłach teselacji Delauney, które przekładają się również na różne opisy przeciągnięć podprzestrzeni. Zauważ, że metoda Voronoi również podlegałaby ogólnemu opisowi podziału i podboju ze względu na jej podział na płaszczyzny, który powoduje etap budowy O (n log n).

Podstawowym rozwiązaniem tego problemu jest:

1. Weź zestaw A i zbuduj efektywną strukturę zapytań Najbliższego sąsiada do wyboru. Ten etap budowy to O (n log n) [patrz twierdzenie 4].
2. Dla każdego elementu w B zapytaj strukturę A o najbliższego sąsiada. Każde zapytanie ma wartość O (log n) [patrz twierdzenie 15, ustalony wymiar], więc całkowity czas zapytania dla wszystkich punktów w B wynosi O (n log n).
3. Po uzyskaniu wyniku dla najbliższego punktu A do każdego B, umieść go w strukturze uporządkowanej na odległość. To jest O (log n) wstaw każdy wynik lub O (n log n) dla wszystkich.
4. Po obejrzeniu wszystkich B możesz szybko (O (1)) uzyskać punkt B w uporządkowanej strukturze z najmniejszą odległością sąsiadującą do punktu w A.

Jak widać patrząc na złożoność każdego kroku, całkowita złożoność wynosi O (n log n). Dla współczesnego czytelnika, który nie patrzy na klasyczne artykuły, jest to omówione w wielu książkach z algorytmami, np. „Podręcznik projektowania algorytmów” Skieny.

Nie jestem pewien, czy mam rację, ale ten problem jest bardzo podobny do problemów, które można rozwiązać za pomocą programowania liniowego w geometrii obliczeniowej. Jednak redukcja do LP nie jest prosta. Również mój problem wygląda na znalezienie najcieńszego punktu pomiędzy dwoma zestawami punktów, które oczywiście można rozwiązać za pomocą LP w przestrzeni dwuwymiarowej.

Dolna granica tego problemu to w algebraicznym modelu drzewa decyzyjnego. Podam tutaj przybliżony szkic tego dowodu.$O(n*\log{n})$

Zmniejszymy wystąpienie problemu odróżnienia elementu E do C.

• Dane wejściowe do E: $S = \{a_1, a_2, a_3,...,a_n\}$
• Niech > 0 będzie małą frakcją$\epsilon$
• A = ,$\{(a_i,0) : 1 \leq i \leq n\}$$B = \{(a_i + \epsilon) : 1 \leq i \leq n\}$
• Teraz, jeśli uda nam się znaleźć najkrótszą odległość (d) między zbiorami A i B. Możemy rozwiązać problem odróżnienia elementu w dodatkowym czasie w następujący sposób $O(n)$
  • Zestaw ma duplikat wtedy i tylko wtedy, gdy d =$S$$\epsilon$

Wiemy, że dolna granica środowiska wykonawczego w celu podjęcia decyzji o problemie z odrębnością elementów to . Dlatego redukcja dolnej granicy dotyczy również naszego problemu.$O(n*\log{n})$