Secondary Polytope and Secondary Power Diagram


如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

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

补充文件

附件文件
动作
1. JATS XML

版权所有 © Pleiades Publishing, Ltd., 2019