Złożoność znalezienia piłki, która maksymalizuje liczbę leżących w niej punktów

Biorąc pod uwagę zbiór punktów $x_1, \ldots, x_n \in \mathbb{R}^2$ i promień . Co jest złożonością znalezienia punktu o większej liczbie punktów w odległości mniejszej niż . Np. Ten, który maksymalizuje ? $r$ $r$ $\sum_{i=1}^n \mathbb{1}_{\|x - x_i\| \leq r}$

Algorytm brutalnej siły polegałby na przejściu każdego punktu i zliczeniu liczby punktów znajdujących się w odległości mniejszej niż $r$ . Dałoby to złożoność $\mathcal{O}(n^2)$ .

Czy istnieje lepsze podejście?

algorithms complexity-theory computational-geometry

— Manuel
źródło

Czy patrzyłeś na drzewa czworokątne i drzewa binarne dzielące drzewa? Spodziewałbym się, że mogą dać algorytm bardziej wydajny w praktyce, chociaż nie wiem, jaki byłby najgorszy przypadek asymptotycznego czasu działania.

— DW

(Środek tytułu ballz tytułu musi pochodzić ze zbioru?) Jednym z pomysłów może być oszacowanie, czy promień jest niewielki w porównaniu ze średnią odległością do najbliższego sąsiada, czy też rzędu średnicy (i rozważyć podejścia do tych ekstremów (przeciągnięcie samolotu dla małego ) i szeroka przestrzeń pomiędzy nimi).

r

$r$

— greybeard,

Środek piłki powinien być ale jeśli istnieje lepszy algorytm bez tego warunku, jestem również zainteresowany.

x_{i}

$x_i$

— Manuel,

Wygląda to na szybszy niż algorytm dla problemu zliczania zasięgu kulek jest nieznany. Jeśli jednak możesz zaakceptować nieprecyzyjną odpowiedź, możesz przybliżyć dysk za pomocą zestawu kwadratów o różnej orientacji. Dla każdej orientacji musisz zbudować drzewo zasięgu ( en.wikipedia.org/wiki/Range_tree ), które pozwoli ci policzyć wszystkie punkty w kwadracie w czasie (k - liczba wynikowych punktów).

O (n)

$O(n)$

O (l o g^{2} (n) + k)

$O(log^2(n) + k)$

— HEKTO,

@HEKTO Czy sugerujesz zbudowanie struktury cost celu zapytania, czy punkt leży w prostokącie o koszcie ? Następnie przejrzyj wszystkie punkty, aby policzyć, ile innych punktów znajduje się w przybliżonej piłce? Mogłoby to działać, ale jaka byłaby pamięć potrzebna do takiej struktury danych? czy byłby niższy niż ?

O (n \log (n))

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

O (l o g^{2} (n) + k)

$\mathcal O (log^2(n) + k)$

O (n^{2}))

$\mathcal O (n^2))$

— Manuel,

Odpowiedzi:

Wygląda na to, że algorytm podliniowy dla problemu zliczania zasięgu kulki nie jest jeszcze znany.

Jeśli jednak możesz zaakceptować nieprecyzyjną odpowiedź, możesz przybliżyć dysk za pomocą zestawu kwadratów o różnej orientacji. Dla każdej orientacji musisz zbudować Drzewo zasięgu , które pozwoli ci policzyć wszystkie punkty wewnątrz kwadratu w czasie czas (k - liczba wynikowych punktów). $O(log^2(n)+k)$

Każde drzewo zakresu będzie wymagało pamięci , im lepsze przybliżenie, tym więcej orientacji należy użyć. Na przykład dwie orientacje dają ośmiokąt , który przybliża dysk z błędem powierzchni mniejszym niż 6%. $O(n \cdot log(n))$

— HEKTO
źródło

Odpowiedź nie jest taka prosta, istnieje zaawansowane badanie tego pytania w teorii złożoności; wydaje się, że jest badany np. jako następujący problem, który koncentruje się wokół szybkich zapytań „zliczania zakresu sferycznego”. Tak, możliwe są ulepszone granice teoretyczne, ale wydają się to abstrakcyjne algorytmy, które nie zostały przez nikogo zaimplementowane. Jeśli chcesz rzeczywistych implementacji, to inne pytanie.

„Kompromisy czasoprzestrzenne dla przybliżonego zliczania zasięgu sferycznego” / Arya, Malamatos, Mount

— vzn
źródło