On Tuesday, February 9, 2016 at 6:06:03 PM UTC+1, bartekltg wrote:
> On 09.02.2016 14:59, M.M. wrote:
> > On Tuesday, February 9, 2016 at 2:42:57 PM UTC+1, Adam M wrote:
> >> Problem jest ciekawy i metoda rozwiazania zelzy do ilosci punktow:
> >> - przy malej ilosci punkow metoda brut-froce lub kazda z wyzej wymienionych
metod poradzi sobie calkiem niezle
> >> - przy duzej ilosci punktow lepsze jest podejscie graficzno-matematyczne.
> >> tworzymy graficzna reprezentacje rozlozenia punktow i lagorytmy analizy obrazu
pozwalaja wybrac nam wrunki graniczne do przeszukiwania (miejsca gdzie jest
najwieksze zageszczenie punktow - najbardziej ciemne miejsca). Metoda ta jednak ma
jedna podstawowa wade - gdy rozmieszczenie punktow jest losowo rownomierne (bialy
szum) graficzna metoda wyznaczenia warunkow brzegowych wyszukiwania padnie na twarz -
ale w tym przypadku chyba kazda metoda padnie na twarz i losowe wybranie punktu
bedzie najlepsze/najtansze obliczeniowo (bo i tak punkty sa rozlozone losowo ale
rownomiernie ;-) )
> >
> >
> > Czy moje założenie, że optymalne rozwiązanie musi mieć na obwodzie okręgu 3
> > punkty, jest prawdziwe?
>
> Tak.
> Na płaszczyźnie;-)
>
> I to daje rozwiązanie n^4, przy jakimś sprytnym sposobie zliczania
> punktów w okręgu nieco mniej.
>
> Jeśli zaczepisz się o dwa punkty i zwiększasz promień,
> wygląda na to, ze da się w n^3 log(n)
>
> W metryce miejskiej to ładniej widać. Zaczepiasz się górnym
> i lewym bokiem o dowolną parę, dodajesz tyle punktów,
> ile potrzeba, dostajesz w wyniku rozmiar kwadratu.
>
>
> Przy okręgach pewnym ułatwieniem będzie zauważanie, że
> dwa sposród obowiązkowych 3 punktów na promieniu są
> oddalone o co najmniej 120deg.
>
> Ostatecznie:
> wybieram dwa punkty. A i B. Są one na okręgu.
>
> Dla każdego innego punktu C wyznaczam promień okręgu,
> w którym się on jeszcze mieści. Tu trzeba się skupić.
>
> Najmniejszy promień jest jak odległość |AB|
> i może rosnać w obie strony. Okręgi można to sobie
> parametryzować kątem, odległosćią od |AB|, co tak kto lubi,
> byleby łatwo zyanczać środek takiego okręgu i jego promień.
>
> niech będzie to d, odelgłość ś(c)odka okręgu od AB.
> R = sqrt(d^2 + (|AB|/2)^2), środek też łatwo wyznaczyć.
>
> Co istotne, d ma znak, dla dodatnich niech okrąg puchnie w prawo,
> dla ujemnych - w lewo.
>
> Każdy punkt C ma wartość _jedną_ (*) krytyczną d. Po jednej jej stronie
> jest w okręgu, po drugiej jest poza.
>
> W czasie O(n) wyzanczamy d dla każdego c.
> W czasie O(n log (n)) sortujemy je.
>
> W czasie O(n) przechodzimy powstałą tabelkę dwoma wskaźnikami,
> zmieniając d. Aktualizujemy wartość promienia, jeśli jest mniejszy
> i mamy >=50% miast.
>
> Wszystko powtorzyliśmy O(n^2), łącznie mamy więc
> O(n^3 log n)
>
> Nie jest źle. A można wprowadzić sporo obcięć,
> jak te z warunku o 120deg czy nie przeszukiwać d dla których
> R jest większe niż już znalezione, i, co ważniejsze, nie brać
> punktów A,B, które są oddalone o więcej niż aktualnie najlepsze R.
> To ostatnie sporo poprawi, jeśli szybko znajdziemy przyzwoite
> rozwiązanie.
>
>
> *) uwagal na punkty leżące wewnętrz odcinka AB:)

Zapomniałem w pośpiechu wymnożyć złożoność przez log(N).
Ma ktoś ochotę zaimplementować ten algorytm?

Pozdrawiam