2. přednáška
Překryvy map - algoritmus pro nalezení průsečíků množiny úseček
Pro danou množinu úseček najde algoritmus všechny jejich průsečíky, navíc ke každému průsečíku uvede všechny úsečky, na kterých leží. Jde o tzv. "sweep line algorithm". Algoritmus je citlivý na velikost výstupu, jeho časová náročnost je O((n+k) log n), kde n je počet úseček a k počet průsečíků. Zhruba lze algoritmus popsat takto: vodorovnou přímku posouváme shora dolů, zastavujeme se v tzv událostech, tj. koncových bodech úseček a v průsečících, a počítáme průsečíky úseček, které protínají naši přímku v blízkosti dané události. Přitom průsečíky nad přímkou jsou již známé. Potřebné struktury: fronta událostí Q tvořená zpočátku koncovými body úseček, postupně se přidávají vypočtené průsečíky pod přímkou. Po průchodu událostí je tato z fronty vymazána. Pro každou událost p máme binární vyvážený strom T(p), který určuje v jakém pořadí protínají úsečky zametací přímku těsně pod událostí p. Se změnou události se tento strom rovněž mění.
Pseudokódy algoritmů najdete na stranách 3-5 následujícího souboru