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:)

pzdr
bartekltg


pzdr
bartekltg