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