Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
A Duality Transform for Constructing Small Grid Embeddings of 3D Polytopes
verfasst von : Alexander Igamberdiev, André Schulz
Erschienen in: Graph Drawing
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\mathcal{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
$\mathcal{C}$
can be realized on a polynomial size grid as well.