Secondary polytope and secondary power diagram

Гениальная конструкция Гельфанда, Капранова и Зелевинского характеризует триангуляции заданных точек таким образом, что все регулярные триангуляции образуют выпуклый многогранник, который называется вторичным. Вторичный многогранник можно рассматривать как взвешенную триангуляцию Делоне в пространстве всех возможных регулярных триангуляций. Естественно, у него должна быть двойственная диаграмма. В данной работе предлагается явное построение вторичной силовой диаграммы, которая представляет собой силовую диаграмму пространства всех возможных силовых диаграмм с непустыми граничными ячейками. Вторичная силовая диаграмма является альтернативным доказательством классической теоремы вторичного многогранника, основанной на теории Александрова. Кроме того, теория вторичных силовых диаграмм показывает, что недегенерированную регулярную триангуляцию можно преобразовать в другую недегенерированную регулярную с помощью последовательности бизвездных модификаций так, что все промежуточные триангуляции также являются недегенерированными и регулярными. В качестве приложения этой теории предлагается алгоритм триангуляции специального класса трехмерных невыпуклых многогранников без использования дополнительных вершин. Показано, что временная сложность алгоритма равна $O({{n}^{3}})$.