Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości grup
dyskusyjnych:n9l2s2$s8s$...@n...news.atman.pl...
> To szukasz algorytmu, czy heurystyki?

Jak zwał tak zwał.

Po prostu /być/ /może/ da się (?) skonstruować patologiczny rozkład, dla
którego algorytm z rzutowaniem będzie O(N**4) czy jakiś taki.

Na przykład dla bardzo dużej ilości punktów rozmieszczonych równomiernie na
okręgu nie ma
koła o wyraźnie mniejszym promieniu (niż promień tego okręgu) które
zawierałoby co najmniej połowę zadanych punktów.

Ale przewiduję, że dla niezłośliwych rozkładów będzie O(N log N), czyli tyle
co sortowanie.

Jeszcze raz - wyobraź sobie że już masz rozwiązanie - i że rzutujesz i
punkty, i to rozwiązanie, na przestrzenie jednowymiarowe.