3622
правки
Изменения
м
→Свойства Straight skeleton
|statement=<tex> S(P) </tex> является деревом, содержит <tex> n </tex> граней, не более <tex> n - 2 </tex> внутренние вершины и не более <tex> 2 n - 3 </tex> рёбер.
|proof=
Каждая грань <tex> f(e) </tex> начинается начинает образовываться во время стягивания ребра <tex> e </tex>, и даже если на ребре произошёл <tex> split\ event </tex>, сама грань не могла разделиться. Построение грани <tex> f(e) </tex> завершается, когда ребро <tex> e </tex> полностью стягивается. И это ребро дальше не может появиться снова, поэтому граней в <tex> S(P) </tex> столько, сколько сторон в многоугольнике, то есть ровно <tex> n </tex>.
То, что <tex> S(P) </tex> является деревом, легко доказывается по индукции. База верна, когда внутренняя вершина всего одна. Тогда у <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> листьями будут вершины многоугольника. Такой граф очевидным образом будет деревом. Если в <tex> \mathrm{straight}\ \mathrm{skeleton}\ k </tex> внутренних вершин, то рассмотрим самый первый <tex> edge\ event</tex>. Он закончился в какой-то внутренней вершине <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>, у неё есть смежные листья {{---}} вершины, инцидентные этому ребру, {{---}} и из неё достижимы другие <tex> \mathrm{straight}\ \mathrm{skeleton}' </tex>ы, с не более чем <tex> k - 1 </tex> внутренними вершинами, и они являются деревьями по предположению индукцию. Тогда получаем, что <tex> S(P) </tex> для <tex> k </tex> вершин тоже будет деревом.
