Удаляем это множество из карты и добавляем новые узлы появившиеся из-за <tex>s_i</tex> в поисковой структуре
Аналогично для просто карты
===Поиск трапецоидов, которых пересекает отрезок===
LookforTrapezoid(<tex>s_i</tex> - segment)
Запоминаем левый и правый конец <tex>s_i</tex>
Делаем запрос на левый конец в карте.
j <tex>\leftarrow</tex> 0;
while q <tex>\in</tex> правый от rightp(трапецоид_j)
do if rightp(трапецоид_j) над <tex>s_i</tex>
then ставим трапецоид_(j+1) нижним правым соседом трапецоид_j.
else ставим трапецоид_(j+1) верхним правым соседом трапецоид_j.
j <tex>\leftarrow</tex> j+1
==Ссылки==
[http://graphics.stanford.edu/courses/cs268-09-winter/ Lecture notes from stanford, Seidel]
