Из техничких разлога садржај читалишта можете пратити искључиво на латиници.

Line arrangement problem

Line arrangement, tj. raspored linija u geometriji je podela ravni formirana kolekcijom linija. Po Zone teoremi određivanje ovog rasporeda zahteva O(n2) vreme i može se dobiti jednostavnim inkrementalnim algoritmom koji dodaje liniju po liniju, medjutim taj algoritam zahteva O(n2) prostor. Postoje problemi koji ne zahtevaju čuvanje celog rasporeda linija, tj. dovoljno je posmatrati taj raspored dok se pravi, i to je bila motivacija za razvijanje algoritamske tehnike zvane topological sweeping.

 

Edelsbrunner i Guibas su 1986. godine razvili ovu tehniku koja spade u klasične algoritme Računarske geometrije. Algoritam prebriše n linija topološkom linijom i zahteva O(n2) vreme i samo O(n) dodatnog prostora. Osnovna tehnika je striktno planarna, medjutim ima primena i u višedimenzionim prostorima.
E. Rafalin, D. Souvaine i I. Streinu su dopunili ovaj algoritam definisanjem ponašanja u specijalnim slučajevima kada postoje paralelne linije, i kada se više linija seku u jednoj tački. Ta implementacija zadržava vremensku i prostornu kompleksnost.

Topološko prebrisavanje može doprineti efikasnosti implementacijama raznih algoritama za analizu podataka, i cilj ovog diplomskog rada je pregled i objedinjavanje dosadašnjih tehnika u implementaciji ovog algoritma.

Autor: Đorđe Jovanović 

Mentor rada: Dr Dragan Urošević

Ovde pročitajte rad u celosti

Рачунарски факултет Рачунарски факултет 011-33-48-079