A Duality Transform for Constructing Small Grid Embeddings of 3D Polytopes

Igamberdiev, Alexander and Schulz, André (2013) A Duality Transform for Constructing Small Grid Embeddings of 3D Polytopes. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 173-184(Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_16).

Full text not available from this repository.

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ère matrices and the Maxwell–Cremona lifting method. As our main result we show that every truncated 3d polytope with n vertices can be realized on a grid of size polynomial in n. Moreover, for a class C of simplicial 3d polytopes with bounded vertex degree, at least one vertex of degree 3, and polynomial size grid embedding, the dual polytopes of C can be realized on a polynomial size grid as well.

Item Type: Conference Paper
Classifications: P Styles > P.060 3D
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1373

Actions (login required)

View Item View Item