Veröffentlichung

Titel:

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

AutorInnen:

Alexander Igamberdiev
André Schulz

Kategorie:

Artikel in Zeitschriften

erschienen in:

Computational Geometry, Vol. 56, 2016, pp. 19-36

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^{3\Delta + 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.

Download:

arXiv

BibTeX-Eintrag:

@article{DBLP:journals/comgeo/IgamberdievS16, author = {Alexander Igamberdiev and Andr{\'{e}} Schulz}, title = {A duality transform for constructing small grid embeddings of 3d polytopes}, journal = {Comput. Geom.}, volume = {56}, pages = {19--36}, year = {2016} }