3622
правки
Изменения
м
→Свойства Straight skeleton
'''База:''' многоугольник является треугольником, в его <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> будет одна внутренняя вершина {{---}} точка пересечения биссектрис, листьями будут вершины треугольника. Такой граф, очевидно, будет деревом.
'''Переход:''' пусть для всех многоугольников с количеством вершин меньше <tex>k</tex> <tex>\mathrm{straight}\ \mathrm{skeleton} S(P)</tex> будет деревом. Рассмотрим самый первый <tex>event</tex> в многоугольнике из <tex>k</tex> вершин.
* Если это <tex>edge\ event</tex>, то появится новая вершина, которую мы соединим с инцидентными ребру вершинами, а также с какой-то вершиной <tex>\mathrm{straight}\ \mathrm{skeleton} </tex> полигона из <tex>k - 1</tex> вершин. Получившийся граф будет деревом.
* Если это <tex>split\ event</tex>, то новая вершина соединяется с одной вершиной исходного полигона и с двумя вершинами <tex>\mathrm{straight}\ \mathrm{skeleton} </tex> для полигонов, в которых меньше <tex> k </tex> вершин. В этом случае также получаем дерево.
