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

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

Описание

Более подробно, разворачивание звезды получается из многогранника выбрав отправную точку на поверхности , в общая позиция, что означает, что существует единственная кратчайшая геодезическая из для каждого вершина из .[2][3][4]Многоугольник звезды получается путем разрезания поверхности вдоль этих геодезических и развернуть полученную поверхность разреза на самолет. Полученная форма образует простой многоугольник в плоскости.[2][3]

Звездное развертывание может быть использовано как основа для полиномиальное время алгоритмы решения различных других задач, связанных с геодезическими на выпуклых многогранниках.[2][3]

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

Развертывание звезды следует отличать от другого способа разрезания выпуклого многогранника на простую многоугольную сетку, т.е. источник разворачивается. Развертывание источника разрезает многогранник в точках, которые имеют несколько одинаковых коротких геодезических относительно данной базовой точки. , и образует многоугольник с в его центре, сохраняя геодезические от . Вместо этого разворачивающаяся звезда разрезает многогранник по геодезическим и образует многоугольник с несколькими копиями в его вершинах.[3] Несмотря на их названия, раскрытие источника всегда производит звездообразный многоугольник, но разворачивающаяся звезда - нет.[1]

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

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

Рекомендации

  1. ^ а б Демейн, Эрик; О'Рурк, Джозеф (2007), «24,3 звезды разворачиваются», Геометрические алгоритмы складывания, Cambridge University Press, стр. 366–372, ISBN  978-0-521-71522-5
  2. ^ а б c Аронов Борис; О'Рурк, Джозеф (1992), «Неперекрытие разворачивающейся звезды», Дискретная и вычислительная геометрия, 8 (3): 219–250, Дои:10.1007 / BF02293047, МИСТЕР  1174356
  3. ^ а б c d е Агарвал, Панкадж К.; Аронов Борис; О'Рурк, Джозеф; Шевон, Екатерина А. (1997), "Звездное развертывание многогранника с приложениями", SIAM Журнал по вычислениям, 26 (6): 1689–1713, Дои:10.1137 / S0097539793253371, МИСТЕР  1484151
  4. ^ Чен, Цзиньдун; Хан, Ицзе (1990), «Кратчайшие пути на многограннике», Труды 6-го ежегодного симпозиума по вычислительной геометрии (SoCG 1990), ACM Press, Дои:10.1145/98524.98601, S2CID  7498502
  5. ^ Ито, Джин-ичи; О'Рурк, Джозеф; Вилку, Костин (2010), "Звезда, раскрывающая выпуклые многогранники с помощью квазигеодезических петель", Дискретная и вычислительная геометрия, 44 (1): 35–54, Дои:10.1007 / s00454-009-9223-х, МИСТЕР  2639817
  6. ^ Киазик, Стивен; Любив, Анна (2016), «Звезда, разворачивающаяся по геодезической кривой», Дискретная и вычислительная геометрия, 56 (4): 1018–1036, Дои:10.1007 / s00454-016-9795-1, HDL:10012/8935, МИСТЕР  3561798, S2CID  34942363
  7. ^ Алам, штат Мэриленд Ашрафул; Стрейну, Илеана (2015), «Полигоны, разворачивающиеся по звездам», Ботана, Франциско; Куарежма, Педро (ред.), Автоматическая дедукция по геометрии: 10-й международный семинар, ADG 2014, Коимбра, Португалия, 9-11 июля 2014 г., отредактированные избранные статьи, Конспект лекций по информатике, 9201, Springer, стр. 1–20, Дои:10.1007/978-3-319-21362-0_1, МИСТЕР  3440706