Secondary Polytope and Secondary Power Diagram
- Autores: Na Lei 1, Chen W.2, Luo Z.3, Si H.4, Gu X.5
-
Afiliações:
- DUT-RU ISE, Dalian University of Technology
- School of Software Technology, Dalian University of Technology
- Key Laboratory for Ubiquitous Network and Service Software of Liaoning Province
- Weierstrass Institute for Applied Analysis and Stochastics
- Department of Computer Science, Stony Brook University
- Edição: Volume 59, Nº 12 (2019)
- Páginas: 1965-1981
- Seção: Article
- URL: https://journals.rcsi.science/0965-5425/article/view/180910
- DOI: https://doi.org/10.1134/S0965542519120121
- ID: 180910
Citar
Resumo
An ingenious construction of Gel’fand, Kapranov, and Zelevinsky [5] geometrizes the triangulations of a point configuration, such that all coherent triangulations form a convex polytope, the so-called secondary polytope. The secondary polytope can be treated as a weighted Delaunay triangulation in the space of all possible coherent triangulations. Naturally, it should have a dual diagram. In this work, we explicitly construct the secondary power diagram, which is the power diagram of the space of all possible power diagrams with nonempty boundary cells. Secondary power diagram gives an alternative proof for the classical secondary polytope theorem based on Alexandrov theorem. Furthermore, secondary power diagram theory shows one can transform a nondegenerated coherent triangulation to another nondegenerated coherent triangulation by a sequence of bistellar modifications, such that all the intermediate triangulations are nondegenerated and coherent. As an application of this theory, we propose an algorithm to triangulate a special class of 3d nonconvex polyhedra without using additional vertices. We prove that this algorithm terminates in \(O({{n}^{3}})\) time.
Palavras-chave
Sobre autores
Na Lei
DUT-RU ISE, Dalian University of Technology
Email: wei.chen@mail.dlut.edu.cn
República Popular da China, Dalian, 116620
Wei Chen
School of Software Technology, Dalian University of Technology
Autor responsável pela correspondência
Email: wei.chen@mail.dlut.edu.cn
República Popular da China, Dalian, 116620
Zhongxuan Luo
Key Laboratory for Ubiquitous Network and Service Software of Liaoning Province
Email: wei.chen@mail.dlut.edu.cn
República Popular da China, Dalian, 116620
Hang Si
Weierstrass Institute for Applied Analysis and Stochastics
Email: wei.chen@mail.dlut.edu.cn
Alemanha, Berlin, 10117
Xianfeng Gu
Department of Computer Science, Stony Brook University
Email: wei.chen@mail.dlut.edu.cn
Estados Unidos da América, Stony Brook, NY 11794
Arquivos suplementares
