Kilka tysiecy punktow, z ktorych nalezy znaleŹĆ pare pkt ktorych odleglosc jest minimalna i pare z max odlegloscia...ale nie porownywac odleglosci kazdej dwojki pkt... brzmi banalnie...kilka sposobow wymyslilam ale zaden nie wytrzymywal bezblednosci za kazdym razem...moze istnieje jakis algorytm genetyczny?? albo jakis calkiem normalny???to jest tylko fragment zadania ale bez przeskoczenia go nie moge nic zrobic....moze ktos ma jakis pomysl??
0
0
Istnieje algorytm znajdujący najbliżej znajdujące się punkty, działający w czasie O(n lg n). Opiera się na zasadzie dziel i zwyciężaj, opracowany przez Shamosa, a opisany we "Wstępie do algorytmów", w rozdz. 33.4.
Co do największej odległości, najbardziej odległe punkty muszą leżeć na otoczce wypukłej danego zbioru. Znalezienie otoczki wypukłej zbioru: np. algorytm Grahama (O(n lg n)), wyszukanie pary najbardziej oddalonych punktów na wielokącie wypukłym: O(n). Co w sumie daje O(n lg n). :]
0
możesz powiedzieć jak O(n) znaleźć na otoczce te najodleglejsze punkty? bo tego jakoś nie znalazłem :)
0
Ten algorytm także został opracowany przez Shamosa. Np. tutaj http://cgm.cs.mcgill.ca/~orm/rotcal.html jest jego opis wraz z pseudokodem.