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

DOI10.1016/J.COMGEO.2016.03.004zbMATH Open1381.52017arXiv1402.1660OpenAlexW1946180610MaRDI QIDQ679743FDOQ679743

Authors: Alexander Igamberdiev, André Schulz 

Publication date: 19 January 2018

Published in: Computational Geometry (Search for Journal in Brave)

Abstract: 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`ere 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 O(n^{9log(6)+1}). Moreover, for every simplicial 3d polytope with n vertices with maximal vertex degree {Delta} and vertices placed on an L x L x L grid, a dual polytope can be realized on an integer grid of size O(n L^{3Delta + 9}). This implies that for a class C of simplicial 3d polytopes with bounded vertex degree and polynomial size grid embedding, the dual polytopes of C can be realized on a polynomial size grid as well.

Full work available at URL: https://arxiv.org/abs/1402.1660

Recommendations

• A Duality Transform for Constructing Small Grid Embeddings of 3D Polytopes
• A duality transform for realizing convex polytopes with small integer coordinates
• Small grid embeddings of 3-polytopes
• Embedding 3-polytopes on a small grid

zbMATH Keywords

lattice polytopesconvex polytopesgraph representationgraph drawing3D polytopesdual polytopegrid embeddinginteger realization

Mathematics Subject Classification ID

Three-dimensional polytopes (52B10) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20)

Cites Work

• Realization spaces of polytopes
• On the number of spanning trees a planar graph can have
• How to draw a planar graph on a grid
• Steinitz representations of polyhedra and the Colin de Verdière number
• On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
• Strictly convex drawings of planar graphs
• Drawing 3-polytopes with good vertex resolution
• Small grid embeddings of 3-polytopes
• A quantitative Steinitz' theorem
• A paradigm for robust geometric algorithms
• An Asymptotic Expression for the Number of Solutions of a General Class of Diophantine Equations

Cited In (2)

• A duality transform for realizing convex polytopes with small integer coordinates
• A Duality Transform for Constructing Small Grid Embeddings of 3D Polytopes

This page was built for publication: A duality transform for constructing small grid embeddings of 3d polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q679743)