2014/02/07 by Alexander Igamberdiev, Igamberdiev, Alexander, André Schulz +1
Computer Science · Engineering · Mathematics · #05C62 #52B10 #52B20 #68R10 #Algorithms and Data Compression #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #I.3.5 #Metric Geometry (math.MG) #Optimization and Packing Problems #Tensor decomposition and applications #acm:05C62 #acm:52B10 #acm:52B20 #acm:68R10 #cs.CG #graph theory and CDMA systems #math.MG #msc:05C62 #msc:52B10 #msc:52B20 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1402.1660
Full version of the Graph Drawing 2013 conference version, 23 pages, 5 figures
openalex publication_date 2014/02/07 · arxiv created 2016/01/25 · arxiv updated 2016/01/26 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
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 O(n9log(6)+1). Moreover, for every simplicial 3d polytope with n vertices with maximal vertex degree Δ 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 L3Δ+ 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.