Dostałem na zajęciach do wykonania projekt:
"Dla danego zbioru odcinków wyznaczyć wszystkie pary przecinających się odcinków metodą zamiatania."
Niestety nie mogę znaleŹć żadnych informacji na temat tej metody. Czy ktoś mógłby wyjaśnić mi na czym polega metoda zamiatania, lub napisać gdzie mogę znaleŹć jakieś informacje na ten temat
0
0
"wprowadzenie do algorytmow" Cormena, jest caly dzial na ten temat...
0
Pozwole sobie odświeżyć nieco temat i walne z innej beczki: Czy ktoś kiedykolwiek analizował lub implementował optymalny algorytm wyszukiwania wszystkich przecięć w zbiorze odcinków (mowa tu o algorytmie umieszczonym w "AiSD" Diksa Banachowskiego i Ryttera, lub choćby tu www.mpi-inf.mpg.de/~mehlhorn/ftp/EATCSmonograph/chapter8.ps str. 67) i wszystko ładnie śmigało? Po kilku dniach wytężonej pracy z tym algorytmem dochodze do wniosku że jest on po prostu niepoprawny co jest conajmniej dziwne no bo w końcu to klasyka.
Nie wiem już czy to coś nie tak ze mną czy z ww. publikacjami [???] dlatego będe wdzięczny za poratowanie ew. pojaśnienie
aha, autor postu wyżej nie miał racji, w cormenie jest słabsza wersja tego algorytmu wyświetlająca tylko czy w zbiorze jest jakieś przecięcie czy nie.