Line arrangement, тј. распоред линија у геометрији је подела равни формирана колекцијом линија. По Зоне теореми одређивање овог распореда захтева О(n2) време и може се добити једноставним инкременталним алгоритмом који додаје линију по линију, меđутим тај алгоритам захтева О(n2) простор. Постоје проблеми који не захтевају чување целог распореда линија, тј. довољно је посматрати тај распоред док се прави, и то је била мотивација за развијање алгоритамске технике зване topological sweeping.
Edelsbrunner и Guibas су 1986. године развили ову технику која спаде у класичне алгоритме Рачунарске геометрије. Алгоритам пребрише н линија тополошком линијом и захтева О(n2) време и само О(n) додатног простора. Основна техника је стриктно планарна, међутим има примена и у вишедимензионим просторима.
E. Rafalin, D. Souvaine и I. Streinu су допунили овај алгоритам дефинисањем понашања у специјалним случајевима када постоје паралелне линије, и када се више линија секу у једној тачки. Та имплементација задржава временску и просторну комплексност.
Тополошко пребрисавање може допринети ефикасности имплементацијама разних алгоритама за анализу података, и циљ овог дипломског рада је преглед и обједињавање досадашњих техника у имплементацији овог алгоритма.
Аутор: Ђорђе Јовановић
Ментор рада: Др Драган Урошевић