Maksymalny krąg zamykający danego promienia

19

Próbuję znaleźć podejście do następującego problemu:

Biorąc pod uwagę zestaw punktu i promień , znajdź punkt środkowy okręgu, tak aby okrąg zawierał maksymalną liczbę punktów ze zbioru. Czas działania powinien wynosić . $S$ $r$ $O(n^2)$

Na początku wydawało się, że jest to coś podobnego do najmniejszego otaczającego problemu, które można łatwo rozwiązać w . Chodziło o to, aby ustawić dowolną centrum i otaczać cały punkt . Następnie, krok po kroku, zamień koło, aby dotknąć punktów w lewo / w prawo i zmniejsz koło do danego promienia, oczywiście to nie zadziała. $O(n^2)$ $S$

algorithms computational-geometry

— com
źródło

7

Nie wiem jak rozwiązać ten problem w czasie , ale istnieje algorytm . $O(n^2)$ $O(n^2\log n)$

Niech będzie okręgiem, którego środkiem jest , ty punkt, o promieniu . Nietrudno jest stwierdzić, że zestaw punktów może być zamknięty okręgiem o promieniu w punkcie przecięcia z nie jest puste. Co więcej, jeśli nie jest puste, muszą być pewne punkty w leżące na pewnym (granica ). Tak więc dla każdego i każdego punktu na jego wiązaniu próbujemy ustalić, ile kręgów zawiera $C(s_i)$ $s_i$ $i$ $r$ $P = \{p_0, p_1, \ldots, p_m\}$ $r$ $I(P)$ $C(p_0), C(p_1), \ldots, C(p_m)$ $I(P)$ $I(P)$ $\textbf{bd}C(p_i)$ $C(p_i)$ $C(s_i)$ $p$ $p$ . Maksymalna liczba spośród wszystkich $p$ będzie odpowiedzią na ten problem.

Przeanalizujmy punkty w . Istnieje mapowanie jeden na jeden między punktami na a liczbą rzeczywistą w . Dla każdego okręgu przecięcie między i może być reprezentowane przez interwał . Tak więc dla wszystkich kręgów innych niż istnieje co najwyżej przedziałów (niektóre kręgi mogą nie przecinać się z ). Maksymalną liczbę można łatwo znaleźć, sortując wszystkie punkty końcowe interwału, skanując je w kolejności i licząc bieżącą nakładającą się liczbę. Dla każdego $\textbf{bd}C(s_i)$ $\textbf{bd}C(s_i)$ $[0, 2\pi)$ $C(s_j)$ $C(s_j)$ $\textbf{bd}C(s_i)$ $[begin_j, end_j]$ $C(s_i)$ $n-1$ $C(s_i)$ $2(n-1)$ $C(s_i)$ , ten krok można wykonać w czasie i jest takich kół, więc złożoność czasowa tego algorytmu wynosi . $O(n\log n)$ $n$ $O(n^2\log n)$

— Wu Yin
źródło

2

Układ kręgów można konstruować w czasie (z dużym prawdopodobieństwem) przy użyciu standardowego, losowego algorytmu przyrostowego. W rzeczywistości czas działania wynosi , gdzie jest liczbą par przecinających się okręgów. Zobacz swój ulubiony podręcznik geometrii obliczeniowej.

O (n^{2})

$O(n^2)$

O (n \log n + k)

$O(n\log n + k)$

k

$k$

— JeffE

2

Myślę, że trudnymi pytaniami jest wiedza, czy wybrany przez ciebie krąg jest w rzeczywistości „maksymalny” w zestawie. Jedynym sposobem, w jaki mogę to ustalić, jest wypróbowanie wszystkich możliwych kombinacji punktów i przetestowanie rozmiaru okręgu, który je otacza.

Możesz jednak zmniejszyć przestrzeń wyszukiwania, dzieląc najpierw przestrzeń punktów na siatkę kwadratowych komórek o szerokości 2r. Następnie zlokalizuj komórkę o największej gęstości. Ponieważ już zlokalizowałeś jeden okrąg X punktów, możesz stwierdzić, że jeśli koło istnieje z większą liczbą punktów, to musi mieć co najmniej X punktów. I wykorzystaj to jako punkt wyjścia do testowania różnych kombinacji punktów.

Jeśli szukasz tylko zestawu punktów, który prawdopodobnie będzie maksymalny, możesz być w stanie jeszcze bardziej zmniejszyć liczbę kombinacji, które musisz przetestować, wybierając te punkty, które mieszczą się w sąsiedztwie komórek, w których gęstość sąsiedztwa jest większy niż X.

Powiedziawszy to, obie „redukcje” mogą się nie powieść, aw najgorszym przypadku będziesz obliczać koła dla wszystkich możliwych kombinacji punktów.

— putnampp
źródło

1

W Chazelle, B .; Lee, DT's Computing 36, 1-16 (1986), twierdzenie 3 na stronie 15, stwierdza, że maksymalny algorytm znajdowania otaczającego okręgu wymaga kosztu czasu . $O(n^2)$

Myślę, że kluczem jest nadal algorytm konstrukcji wykresu przecięcia , o którym wspominał wcześniej (lub patrz Edelsbrunner, H. (1987), Algorytmy w geometrii kombinatorycznej, rozdział 7). Następnie znalezienie otaczającego okręgu maximun powinno być proste. $O(n^2)$

Najwyraźniej problem ten jest równoznaczny ze znalezieniem punktu objętego maksymalną liczbą danych kręgów i łatwo jest wiedzieć, że tylko te w większości punktów przecięte przez dane n kół należy uznać za kandydatów. (Prowadzi to również bezpośrednio do algorytmu ) $2n^2$ $O(n^2log(n))$

Jednak dzięki zastosowaniu wyżej wspomnianego algorytmu konstrukcyjnego prowadzi on również algorytm dla tego problemu. Ponieważ wykres przecięcia zbudowany z wierzchołków jako punktów przecięcia i krawędzi jako łuków jest wykresem planarnym Eulera. Można więc po prostu podróżować wszystkimi łukami przez cykl Eulera i kolejność łuków indeksowanych przez indeksy okręgów, do których należy, oraz informację, czy jakikolwiek łuk jest „łukiem odchodzącym” (zakrzywionym do tyłu) lub „wejściem w łuk” ( zakrzywione do przodu) dla zarejestrowanego wierzchołka napotkanego podczas przemierzania łuku. $O(n^2)$ $O(n^2)$

Według twierdzenia Jordana wierzchołek przecięcia jest otoczony okręgiem tylko wtedy, gdy napotyka najpierw „łuk odchodzący” należący do tego koła lub ma łuk padający należący do tego koła. Tak więc po całej podróży można łatwo znaleźć maksymalne otaczające koło. Podobnie jest w przypadku decydowania o czasach pokrycia dla punktów z uporządkowanymi przedziałami wzdłuż linii prostej (lub tj. Wersji 1D tego otaczającego problemu), z tym wyjątkiem, że kolejność została już wydana przez podróż. Podczas gdy według formuł Eulera dla wykresu płaskiego, całkowita liczba łuków jest liniowa z liczbą wierzchołków, a ponieważ nie trzeba ponownie rejestrować powiązanych informacji podczas podróży z powrotem do już odwiedzonych wierzchołków, przez uścisk dłoni lemat, całkowity koszt czasu wyniesie . $V + E - F = 2$ $O(n^2)$

— stos99
źródło

Jeśli należy to czytać jako uzupełnienie przyjętej odpowiedzi i nie należy jej czytać samodzielnie (czego nie wiem, ponieważ nie znam tego tematu), powinieneś o tym wyraźnie powiedzieć.

— babou