228
правок
Изменения
→Алгоритм
Считается, что еслли добавлять отрезки рандомно, то время будет хорошим. Почему и какое время будет рассписано дальше.
*Добавили отрезок.
[[Файл:Trpezoidmapbadcaseshagal.jpg|400px|thumb|right|сложный случай]]
Оно произошло в тех трапецоидах которые пересек текущий отрезок или можно сказать, что трапецоид с i-1-ой итерации не будет в i-ой только если его пересек отрезок.
Пусть якобы есть множество трапецоидов <tex>\Delta_0, \Delta_1, \Delta_2 ... \Delta_k</tex> упорядоченное по <tex>s_i</tex>
Пусть <tex>\Delta_(j+1)</tex> один из правых соседей <tex>\Delta_j</tex> Так же при этом не сложно понять каким соседом он является.
Если rightp(<tex>\Delta_j</tex>) лежит выше <tex>s_i</tex>, то сосед нижний и наоборот.
Это значит, что если мы знаем первый трапецоид, то мы можем найти остальные просто обходя по карте соседей справа.
Чтобы найти первый трапецоид нужно просто локализоваться правому концу в текущей карте.
===update===
Рассмотрим подробнее последние две части
По хорошему то как этот происходит просто ужасно и видеть это не хочется, а все потому, что много что добавляется много новых узлов.
<tex>\Delta_0, \Delta_1, \Delta_2 ... \Delta_k</tex>.
==Асимптотика==
