Problem zasięgu (nadajnik i odbiornik)

Próbuję rozwiązać następujący problem z zasięgiem.

Istnieje nadajników o zasięgu 1 km i odbiorników. Zdecyduj w że wszystkie odbiorniki są objęte dowolnym nadajnikiem. Wszystkie reveivers TRANSMITER i jest reprezentowany przez oraz współrzędnych. $n$ $n$ $O(n\log n)$ $x$ $y$

Najbardziej zaawansowane rozwiązanie, z którym mogę skorzystać, zajmuje . Dla każdego odbiornika posortuj wszystkie nadajniki według odległości do bieżącego odbiornika, a następnie weź nadajnik z najkrótszą odległością, a ta najkrótsza odległość powinna wynosić 0,5 km. $O(n^2\log n)$

Ale podejście naiwne wygląda znacznie lepiej w złożoności czasowej . Wystarczy obliczyć całą odległość między wszystkimi parami nadajnika i odbiornika. $O(n^2)$

Nie jestem pewien, czy mogę zastosować algorytmy wyszukiwania zasięgu w tym problemie. Na przykład drzewa kd pozwalają nam znaleźć takie zakresy, jednak nigdy nie widziałem takiego przykładu i nie jestem pewien, czy istnieje rodzaj wyszukiwania zakresów dla kół.

Podana złożoność $O(n\log n)$ zakłada, że rozwiązanie powinno być jakoś podobne do sortowania.

algorithms computational-geometry search-problem

— com
źródło

Jeżeli przewidywany czas

jest w porządku, myślę, że można zbudować

-tree nad nadajnikami (poświęcenie czasu

), a następnie wykonać najbliższego sąsiada zapytanie dla każdego odbiornika (przyjmując średnią czasu

dla każdego odbiornika). To powinno wystarczyć, ale zakładam, że potrzebujesz najgorszej złożoności przypadku. Wydaje się, że kilka sztuczek dla SpeedUp podczas wykonywania wielu najbliższego sąsiada kwerend w sposób

-tree.

O (n \log n)

$O(n \log n)$

k d

$kd$

O (n \log n)

$O(n \log n)$

O (\log n)

$O(\log n)$

k d

$kd$

— utdiscant

Wydaje mi się, że algorytm linii wymiatania może załatwić sprawę: posortuj nadajniki i odbiorniki według współrzędnej X i przejrzyj listę. Niezbędne jest sprytne zarządzanie zestawem wykonalnych nadajników.

— Raphael

@ Rafael, czy mógłbyś rozwinąć nieco więcej, wygląda na to, że w najgorszym przypadku będzie to bardzo powolne.

— com

Myślę, że warto przyjrzeć się algorytmowi Fortune do obliczania diagramu Voronoi w płaszczyźnie. Działa w

, a biorąc pod uwagę schemat Voronoi, twój problem staje się łatwy.

O (n \log n)

$O(n\log n)$

— Syzygy

Aby rozwiązać ten problem, możesz użyć diagramu Voronoi wraz ze strukturą danych Kirkpatrick .

$\mathcal{O}(n \log n)$

$1\ \text{km}$

$\mathcal{O}(\log n)$ $\mathcal{O}(n\log n)$ $\mathcal{O}(n\log n)$

Każda komórka na diagramie Voronoi jest wypukłym wielokątem, być może nieograniczonym.

...

Liczba wierzchołków [na diagramie Voronoi n miejsc] V ≤ 2n-5

- www.cs.arizona.edu

$\Theta(v)$ $v$ $n$ $n$ $\mathcal{O}(n)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$

— Realz Slaw
źródło