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, međutim 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, međutim 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ć