Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości grup
dyskusyjnych:n9l2s2$s8s$...@n...news.atman.pl...
> A B
>
> C
>
> Odległość AB = 1
> odległosc BC = 1.4...1.42
>
> Rzut na odrzucił A. Rozwiązaniem jest {B,C}
> rzut na y odrzucił C, Rozwiązaniem jest {A,B}
>
> Nie widzę, jak ten alborytm teraz zszywa rozwiązanie.

Inteligentnie ;)

Są tylko trzy punkty, więc sprawdzane są małe okręgi o średnicach AB, BC i
AC.

Ale wic w tym że te rzuty, o jakich piszesz, wytypowały punkty A, B, C jako
ważne. Gdyby było więcej punktów,
to większość z nich byłaby odrzucona. I to na etapie kosztującym O(N) po
sortowaniu O(N log N).
Czyli wychodzi O(N log N) na każdą selekcję, selekcje są 2 dla 2D. Dalej
jest O(N log N).