Звезда разворачивается - Star unfolding

В вычислительной геометрии , то звезда разворачивание из выпуклого многогранника является чистой , полученным путем разрезания многогранника вдоль геодезических (кратчайшие) , через его грани. Его также называли внутренним расположением многогранника или развёртыванием Александрова в честь Александра Даниловича Александрова , который первым его рассмотрел.

Описание

Более подробно, звезда разворачивания получается из многогранника , выбрав начальную точку на поверхности , в общем положении , а это означает , что существует единственная кратчайшие геодезическое из каждой вершину из . Многоугольник звезды получается путем разрезания поверхности вдоль этих геодезических и развертывания полученной поверхности разреза на плоскости . Полученная форма образует простой многоугольник на плоскости. ${\ displaystyle P}$${\ displaystyle p}$${\ displaystyle P}$${\ displaystyle p}$${\ displaystyle P}$${\ displaystyle P}$

Развертывание звезды может быть использовано в качестве основы для алгоритмов полиномиального времени для различных других задач, связанных с геодезическими на выпуклых многогранниках.

Связанные развороты

Разворачивание звезды следует отличать от другого способа разрезания выпуклого многогранника на простую многоугольную сетку при разворачивании источника . Развертывание источника разрезает многогранник в точках, которые имеют несколько одинаковых коротких геодезических относительно данной базовой точки , и образует многоугольник с центром в центре, сохраняя геодезические из . Вместо этого разворачивающаяся звезда разрезает многогранник по геодезическим и образует многоугольник с несколькими копиями в его вершинах. Несмотря на их названия, при развертывании источника всегда образуется многоугольник в форме звезды , а при развертывании звезды - нет. ${\ displaystyle p}$${\ displaystyle p}$${\ displaystyle p}$${\ displaystyle p}$

Также изучались обобщения развёртывания звезды с использованием геодезической или квазигеодезической вместо единственной базовой точки. Другое обобщение использует одну базовую точку и систему геодезических, которые не обязательно являются кратчайшими геодезическими.

Ни развертывание звезды, ни развертывание источника не ограничивают свои разрезы краями многогранника. Остается открытым вопрос, можно ли каждый многогранник разрезать и развернуть в простой многоугольник, используя разрезы только по его краям.

Ссылки