Журнал вычислительной математики и математической физики, 2019, T. 59, № 12, стр. 2045-2045
Secondary Polytope and Secondary Power Diagram
Na Lei 1, *, Wei Chen 2, **, Zhongxuan Luo 3, ***, Hang Si 4, ****, Xianfeng Gu 5, *****
1 DUT-RU ISE, Dalian University of Technology
116620 Dalian, China
2 School of Software Technology, Dalian University of Technology
116620 Dalian, China
3 Key Laboratory for Ubiquitous Network and Service Software of Liaoning Province
116620 Dalian, China
4 Weierstrass Institute for Applied Analysis and Stochastics
10117 Berlin, Germany
5 Department of Computer Science, Stony Brook University
11794 Stony, Brook, NY, USA
* E-mail: nalei@dlut.edu.cn
** E-mail: wei.chen@mail.dlut.edu.cn
*** E-mail: zxluo@dlut.edu.cn
**** E-mail: hang.si@wias-berlin.de
***** E-mail: gu@cs.stonybrook.edu
Поступила в редакцию 26.06.2019
После доработки 26.06.2019
Принята к публикации 05.08.2019
Аннотация
Гениальная конструкция Гельфанда, Капранова и Зелевинского характеризует триангуляции заданных точек таким образом, что все регулярные триангуляции образуют выпуклый многогранник, который называется вторичным. Вторичный многогранник можно рассматривать как взвешенную триангуляцию Делоне в пространстве всех возможных регулярных триангуляций. Естественно, у него должна быть двойственная диаграмма. В данной работе предлагается явное построение вторичной силовой диаграммы, которая представляет собой силовую диаграмму пространства всех возможных силовых диаграмм с непустыми граничными ячейками. Вторичная силовая диаграмма является альтернативным доказательством классической теоремы вторичного многогранника, основанной на теории Александрова. Кроме того, теория вторичных силовых диаграмм показывает, что недегенерированную регулярную триангуляцию можно преобразовать в другую недегенерированную регулярную с помощью последовательности бизвездных модификаций так, что все промежуточные триангуляции также являются недегенерированными и регулярными. В качестве приложения этой теории предлагается алгоритм триангуляции специального класса трехмерных невыпуклых многогранников без использования дополнительных вершин. Показано, что временная сложность алгоритма равна $O({{n}^{3}})$.
Полностью статья опубликована в английской версии журнала.
Список литературы отсутствует.
Дополнительные материалы отсутствуют.
Инструменты
Журнал вычислительной математики и математической физики