Logo der Fakultät Logo LG Theoretische Informatik
 

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 | 04.05.2017
FernUni-Logo FernUniversität in Hagen, LG Theoretische Informatik, 58084 Hagen