Sortowanie według odległości euklidesowej

jest zbiorem punktów na płaszczyźnie. Losowy punkt jest podany na tej samej płaszczyźnie. Zadanie to rozwiązać wszystkie przez euklidesową odległość pomiędzy i . $S$ $x \notin S$ $y \in S$ $x$ $y$

Podejście no-mózg jest obliczenie odległości między i dla wszystkich , a następnie posortować je za pomocą dowolnego szybki algorytm. $x$ $y$ $y \in S$

Czy istnieje sposób na przechowywanie lub wstępne przetwarzanie aby proces sortowania stał się szybszy? $S$

cg.comp-geom sorting Alex K.
źródło

Możesz rozważyć siatkę o odpowiednim rozmiarze i grupować punkty według odpowiedniego kwadratu (używając, powiedzmy, tabeli skrótów). Następnie dla niektórych par kwadratów można wywnioskować, że wszystkie punkty z jednego kwadratu są dalej od

niż wszystkie punkty z innego kwadratu. W praktyce może to pomóc.

x

$x$

ilyaraz

„Podejście bez mózgu”, o którym mówiłeś, działa w czasie O (n log n), gdzie n jest liczbą punktów w S, które, jak sądzę, w praktyce jest dość szybkie. Czy chcesz odrzucić współczynnik log n, czy chcesz coś innego, takiego jak sortowanie zewnętrzne ?

Tsuyoshi Ito

Chodzi o to, że mam praktycznie nieograniczony czas na przygotowanie zestawu punktów, ale czas na ich sortowanie jest bardzo ograniczony. To powiedziawszy, każde przyspieszenie standardowego sortowania jest doceniane - nawet jeśli jest to takie samo O (n log n), ale szybsze w najgorszym przypadku (lub najlepszym przypadku, lub cokolwiek innego).

Alex K.,

Na przykład, jeśli przechowuję S jako drzewo 2-d, mogę znaleźć najbliższego sąsiada w czasie O (log n). Może istnieje podobne rozwiązanie dla mojego zadania. Nie jestem wielkim ekspertem w dziedzinie struktur danych przestrzennych - a jest ich tak wiele - z łatwością mógłbym tego przegapić.

Alex K.,

Odpowiedzi:

Rozwiązanie 1: Znajdź prostopadłe dwusieczne między parami punktów i konstruuj układ tych linii. Układ ma komórek, w których porządek sortowania jest stały. Zbuduj więc strukturę danych lokalizacji punktu dla aranżacji i udekoruj każdą komórkę posortowaną kolejnością, która ma zostać zwrócona dla punktów w tej komórce. Posortowane zamówienia między sąsiednimi komórkami różnią się tylko pojedynczą transpozycją, więc można użyć trwałej struktury danych, aby umożliwić reprezentacjom tych posortowanych zamówień współdzielenie przestrzeni. Całkowita przestrzeń wynosi a czas zapytania wynosi $\Theta(n^2)$ $\Theta(n^4)$ $O(n^4)$ . $O(\log n)$

Rozwiązanie 2: Wybierz losową próbkę tych samych prostopadłych dwusiecznych, skonstruuj ich układ i podziel każdą komórkę aranżacyjną pionowymi segmentami linii przez każde skrzyżowanie dwóch próbkowanych linii. Powstały podział ma komórek, z których każda z dużym prawdopodobieństwem jest przecinana przez niespróbkowanych dwusiecznych. Udekoruj każdą komórkę partycji za pomocą prawidłowego uporządkowania punktów widzianych z pewnego x wewnątrz komórki. Całkowita przestrzeń wynosi . $\Theta(n)$ $\Theta(n^2)$ $O(n)$ $O(n^3)$

Teraz, aby wykonać zapytanie, zlokalizuj punkt zapytania na partycji, wyszukaj kolejność przechowywaną w komórce partycji i użyj algorytmu sortowania porównawczego drzewa kartezjańskiego Levcopoulos i Petersson (1989), zaczynając od tej przechowywanej kolejności. Czas dla tego kroku jest proporcjonalny do gdzie jest liczbą punktów, które są poza kolejnością względem punktu . Ale to (każdy niespróbkowany dwusieczny powoduje co najwyżej jedną parę punktów poza kolejnością), więc czas zapytania $\sum_i O(1+\log k_i)$ $k_i$ $y_i$ $\sum k_i$ $O(n)$ to także . $\sum_i O(1+\log k_i)$ $O(n)$

David Eppstein
źródło

PS tutaj jest alternatywny wariant rozwiązania 2, który wykorzystuje tę samą przestrzeń i czas zapytania, ale handluje bardziej skomplikowanym algorytmem przetwarzania wstępnego dla prostszego algorytmu zapytania: 11011110.livejournal.com/233793.html

David Eppstein

Dlaczego

przetwarzania wstępnego, skoro można sortować ze wszystkich

punktów początkowych w czasie

i przechowywać wyniki w tabeli skrótów, używając przestrzeni

do ciągłego wyszukiwania?

n^{4}

$n^4$

n

$n$

O (n^{2} \log n)

$O(n^2\log n)$

O (n^{2})

$O(n^2)$

Dave

Ponieważ istnieją

punkty początkowe z różnymi porządkami sortowania, a nie

Θ (n^{4})

$\Theta(n^4)$

Θ (n^{2})

$\Theta(n^2)$

David Eppstein,

Prawdopodobnie nie będziesz w stanie uciec od czasu w jakikolwiek sposób; nawet regiony obliczania wstępnego odpowiadające wszystkim możliwym porządkom sortowania mogłyby (wydaje mi się) dawać regiony , a zatem znalezienie „twojego” regionu dowolną znaczącą techniką wyszukiwania zajmie czas. ( EDYCJA: $n\log(n)$ $O(n!)$ $O(\log(n!)) = O(n\log(n))$ to jest absolutnie złe; zobacz doskonałą odpowiedź Davida Eppsteina, aby uzyskać więcej informacji!) Z drugiej strony jeden użyteczny sposób na zmniejszenie złożoności - szczególnie, jeśli nie potrzebujesz od razu całego rodzaju, ale po prostu musisz mieć możliwość losowego wyciągnięcia -najbliższego w locie - może odbywać się za pomocą diagramów Voronoi wyższego rzędu: rozszerzenia standardowej komórki Voronoi, które akceptują nie tylko najbliższego sąsiada, ale drugiego najbliższego itd. Artykuł Franka Dehne'a na temat wyszukiwania najbliższego sąsiada, http: //people.scs .carleton.ca / ~ dehne / publications / 2-02.pdf wydaje się być kanonicznym odniesieniem; jego strona główna pod adresem http://www.dehne.carleton.ca/publications zawiera wiele innych artykułów na temat diagramów Voronoi, które mogą być przydatne. $k$

Steven Stadnicki
źródło

Θ (n^{4})

$\Theta(n^4)$

O (n!)

$O(n!)$

Θ (n^{2})

$\Theta(n^2)$

@ David Uważam, że powinieneś zrobić z tego odpowiedź.

James King

Oddelegowany - n! pisałem to źle, ale nie widziałem żadnej sprawy przeciwko. Wkrótce poprawię swoją odpowiedź, aby to poprawić, ale naprawdę chciałbym zobaczyć odpowiedź bardziej bezpośrednią; Dziękuję Ci!

Steven Stadnicki