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

DOI10.1016/J.COMGEO.2016.03.004MaRDI QIDQ679743zbMATH OpenOpenAlexFDO

Authors Alexander Igamberdiev, André Schulz

Publication date 19 January 2018

Published in Computational Geometry (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

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)