A duality transform for constructing small grid embeddings of 3d polytopes

详细信息    查看全文

• 作者：Alexander Igamberdiev ; ^{alexander.igamberdiev@fernuni-hagen.de" class="auth_mail" title="E-mail the corresponding author} ; André ; Schulz ; ^{andre.schulz@fernuni-hagen.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Convex polytopes ; 3D polytopes ; Lattice polytopes ; Graph drawing ; Graph representation
• 刊名：Computational Geometry
• 出版年：2016
• 出版时间：July 2016
• 年：2016
• 卷：56
• 期：Complete
• 页码：19-36
• 全文大小：512 K

文摘

We study the problem of how to obtain an integer realization of a 3d polytope when an integer realization of its dual polytope is given. We focus on grid embeddings with small coordinates and develop novel techniques based on Colin de Verdière matrices and the Maxwell–Cremona lifting method.

We show that every truncated 3d polytope with n   vertices can be realized on a grid of size class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300220&_mathId=si1.gif&_user=111111111&_pii=S0925772116300220&_rdoc=1&_issn=09257721&md5=74063c5c18b60b52a1c1da84d175d887" title="Click to view the MathML source">O(n^9log⁡6+1)class="mathContainer hidden">class="mathCode">$O(n^{9\log 6+1})$. Moreover, for every simplicial 3d polytope with n   vertices with maximal vertex degree Δ and vertices placed on an class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300220&_mathId=si2.gif&_user=111111111&_pii=S0925772116300220&_rdoc=1&_issn=09257721&md5=6dcd039e9a8afa499b85211243874b0d" title="Click to view the MathML source">L×L×Lclass="mathContainer hidden">class="mathCode">$L\times L\times L$ grid, a dual polytope can be realized on an integer grid of size class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300220&_mathId=si3.gif&_user=111111111&_pii=S0925772116300220&_rdoc=1&_issn=09257721&md5=52b3c3501f2c18976d3902795d2bb91a" title="Click to view the MathML source">O(nL^3Δ+9)class="mathContainer hidden">class="mathCode">$O(n{L}^{3\mathrm{\Delta }+9})$. This implies that for a class class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300220&_mathId=si4.gif&_user=111111111&_pii=S0925772116300220&_rdoc=1&_issn=09257721&md5=a912cc0a5ca63afe71f577e48f374b19" title="Click to view the MathML source">Cclass="mathContainer hidden">class="mathCode">$\mathcal{C}$ of simplicial 3d polytopes with bounded vertex degree and polynomial size grid embedding, the dual polytopes of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300220&_mathId=si4.gif&_user=111111111&_pii=S0925772116300220&_rdoc=1&_issn=09257721&md5=a912cc0a5ca63afe71f577e48f374b19" title="Click to view the MathML source">Cclass="mathContainer hidden">class="mathCode">$\mathcal{C}$ can be realized on a polynomial size grid as well.