|
This article is cited in 3 scientific papers (total in 3 papers)
Secondary polytope and secondary power diagram
Na Leia, Wei Chenb, Zhongxuan Luoc, Hang Sid, Xianfeng Gue a DUT-RU ISE, Dalian University of Technology, Dalian, 116620 China
b School of Software Technology, Dalian University of Technology, Dalian, 116620 China
c Key Laboratory for Ubiquitous Network and Service Software of Liaoning Province, Dalian, 116620 China
d Weierstrass Institute for Applied Analysis and Stochastics, 10117 Berlin, Germany
e Department of Computer Science, Stony Brook University, Stony Brook, NY 11794, USA
Abstract:
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.
Key words:
upper envelope, convex hull, power diagram, weighted Delaunay triangulation, secondary polytope.
Received: 26.06.2019 Revised: 26.06.2019 Accepted: 05.08.2019
Citation:
Na Lei, Wei Chen, Zhongxuan Luo, Hang Si, Xianfeng Gu, “Secondary polytope and secondary power diagram”, Zh. Vychisl. Mat. Mat. Fiz., 59:12 (2019), 2045; Comput. Math. Math. Phys., 59:12 (2019), 1965–1981
Linking options:
https://www.mathnet.ru/eng/zvmmf10995 https://www.mathnet.ru/eng/zvmmf/v59/i12/p2045
|
Statistics & downloads: |
Abstract page: | 77 |
|