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 Website
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} }
Christoph Doppelbauer | 20.09.2018