577
правок
Изменения
→Доказательство корректности гамма-алгоритма
== Доказательство корректности гамма-алгоритма ==
Перед доказательством корректности приведем ряд важных вспомогательных лемм и теорем.
Пусть два сегмента <tex>S_{1}</tex> и <tex>S_{2}</tex> называются '''конфликтующими''' относительно уже уложенной части, если:
# грань вмещает каждый из сегментов <tex>S_{1}</tex> и <tex>S_{2}</tex>
# в этих сегментах есть две цепи между контактными вершинами <tex>L_{1}</tex> и <tex>L_{2}</tex> соответственно такие, что их невозможно уложить в одну грань без пересечения
Например, на рис. 1 конфликтующими являются сегменты <tex>S_{1}</tex> и <tex>S_{2}</tex>.
{| cellpadding="2"
| || [[Файл:Гамма-алгоритм8.jpg|thumb|left|520px|Рис. 1. Конфликтующие сегменты.]]
|}
