Пересечение отрезков и прямых

Оценка. Для начала докажем, что больше самопересечений быть не может. Назовём звенья одного направления горизонтальными, а звенья второго направления — вертикальными. Расположим плоскость так, чтобы горизонтальные звенья действительно стали горизонтальными. Заметим сразу две вещи:

каждая точка самопересечения — это пересечение вертикального и горизонтального звена; горизонтальные и вертикальные звенья чередуются, поэтому каждых по штук.

Пронумеруем сверху вниз горизонтальные звенья от до . Посмотрим на звено с номером . Каждое пересекающее его вертикальное ребро должно иметь над ним конец, совпадающий с концов некоторого горизонтального ребра. Горизонтальных рёбер выше всего , поэтому на -м ребре не более точек самопересечений. Эта оценка хорошо работает для от до : на них суммарно не более

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

Для ребра с номером немного улучшим оценку: всего существует вертикальных рёбер, но два из них выходят из концов -го звена, поэтому не могут его пересекать. Итого, на звене не более точек самопересечений. Значит, суммарно их не больше

Пример. Пронумеруем и вертикальные звенья тоже. Пусть -е вертикальное ребро соединяет и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья.

Аналогичный пример для -звенной ломаной на картинке ниже: