Изменения

Чтобы уменьшить объем графа, из него можно удалить ребра, по которым точно не пройдет путь.

{{Лемма

|statement=

Если существуют вершины <tex> A, B, C </tex> одного препятствия и вершина <tex> D </tex> такая, что поворот <tex> DBA </tex> не совпадает с поворотом <tex> DBC </tex>, то ребро <tex> DB </tex> можно удалить. (См. поясняющую картинку справа)

|proof=

Путь проходящий через ребро <tex> BD </tex> будет длиннее, чем через соседей точки <tex> B </tex>, так как по неравенству треугольника <tex> AB + BD < AD </tex>

}}

=== Построение visibility графа ===