Secondary Polytope and Secondary Power Diagram
- 作者: Na Lei 1, Chen W.2, Luo Z.3, Si H.4, Gu X.5
-
隶属关系:
- 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
- 期: 卷 59, 编号 12 (2019)
- 页面: 1965-1981
- 栏目: Article
- URL: https://journal-vniispk.ru/0965-5425/article/view/180910
- DOI: https://doi.org/10.1134/S0965542519120121
- ID: 180910
如何引用文章
详细
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.
作者简介
Na Lei
DUT-RU ISE, Dalian University of Technology
Email: wei.chen@mail.dlut.edu.cn
中国, Dalian, 116620
Wei Chen
School of Software Technology, Dalian University of Technology
编辑信件的主要联系方式.
Email: wei.chen@mail.dlut.edu.cn
中国, Dalian, 116620
Zhongxuan Luo
Key Laboratory for Ubiquitous Network and Service Software of Liaoning Province
Email: wei.chen@mail.dlut.edu.cn
中国, Dalian, 116620
Hang Si
Weierstrass Institute for Applied Analysis and Stochastics
Email: wei.chen@mail.dlut.edu.cn
德国, Berlin, 10117
Xianfeng Gu
Department of Computer Science, Stony Brook University
Email: wei.chen@mail.dlut.edu.cn
美国, Stony Brook, NY 11794
补充文件
