(алгоритм отрезания ушей)
А почему, кстати, его обзывают

? Гарантировано ведь вроде лишь

-- ведь на каждом шаге бог весть, через сколько подшагов очередное ухо встретится.
Это правда, если без опитимизации.
Оптимизация такая - для всех вершин вычисляется валидность диагонали (в совокупности

). Флажки с валидностью собираются в кольцо. При удалении валидной вершины, надо удалить из кольца три значения и вставить два. Эти два надо вычислить. На это уйдёт

. В совокупности, на модификацию кольца тоже уйдёт

.
Ещё одна оптимизация: можно показать, что если "правильно" перемещаться по кольцу, то его вообще можно не вычислять заранее. Но это требует сложного доказательства и никому не интересно потому что сама сложность в

не интересна.