222
правки
Изменения
м
{|align="right"
|-valign="top"
|[[Файл:edgeToDelete.jpg|150px|thumb|right|Удаляем <tex> BD </tex>]]
|[[Файл:edgeNotToDelete.png|150px|thumb|center|Не удаляем <tex> BS </tex>]]
|}
→Visibility graph
{{Лемма
|statement=
[[Файл:edgeToDelete.jpg|150px|thumb|right|Удаляем <tex> BD </tex>]]
Если существуют вершины <tex> A, B, C </tex> одного препятствия и вершина <tex> D </tex> такая, что поворот <tex> DBA </tex> не совпадает с поворотом <tex> DBC </tex>, то ребро <tex> DB </tex> можно удалить. (См. поясняющую картинку справа)
|proof=
[[Файл:edgeNotToDelete.png|200px|thumb|right|Не удаляем <tex> BS </tex>]]
Путь проходящий через ребро <tex> BD </tex> будет длиннее, чем через соседей точки <tex> B </tex>, так как по неравенству треугольника <tex> AB + BD < AD </tex>
}}
=== Построение visibility графа ===
==== Наивный алгоритм. <tex> O(n ^ 3) </tex> ====
