Изменения

Обработка <tex> edge\ event'</tex>ов выполняется с такой же асимптотикой, что как и в алгоритме для выпуклых полигонов. Но из-за того, что в очередь кладутся всевозможные точки свершения , в которых произошли <tex> split\ event'</tex>овы, в ней может оказаться <tex>\mathcal{O}(n^2)</tex> элементов. Хотя обработка <tex> split\ event'</tex>а может занять линейное время от числа вершин (если новая вершина в точке пересечения осталась невыпуклой), это произойдёт только для <tex> split\ event'</tex>ов, которые создают новые вершины <tex> S(P) </tex>, а их <tex>\mathcal{O}(n)</tex> по доказанной [[#lemma1 | лемме]]. Остальные <tex> split\ event'</tex>ы обработаются за <tex>\mathcal{O}(1)</tex> в шаге <tex> 2b </tex>, поэтому итоговая асимптотика составит <tex>\mathcal{O}(n^2 \log n)</tex>.