Representing Polyhedra: Faces are Better than Vertices

Files
TR Number
TR-90-64
Date
1990
Journal Title
Journal ISSN
Volume Title
Publisher
Department of Computer Science, Virginia Polytechnic Institute & State University
Abstract

In this paper, we investigate the reconstruction of planar-faced polyhedra given their spherical dual representation. We prove that the spherical dual representation is unambiguous for all genus 0 polyhedra and that a genus 0 polyhedra can be uniquely reconstructed in polynomial time. We also prove that when the degree of the spherical dual representation is at most four, the representation is unambiguous for polyhedra at any genus. The first result extends the well known result that a vertex or face connectivity graph represents a polyhedron unambiguously when the graph is triconnected and planar in the case of planar-faced polyhedra. The second result shows that when each face of a polyhedron of arbitrary genus has at most four edges, the polyhedron can be recontructed uniquely. This extends the result that a polyhedron can be uniquely reconstructed when each face of the polyhedron is triangular. To obtain this result, we prove that the 4-dimension hypercube, a classic example of ambiguity in the wire frame representation scheme, is unambiguous when the same connectivity graph is viewed as the spherical dual representation of a polyhedron and thus that faces are a better representation than vertices. A result of the reconstruction algorithm is that high level features of the polyhedron are naturally extracted. Both of our results explicitly use the fact that the faces of the polyhedron are planar. We conjecture that the spherical dual representation is unambiguous for polyhedra of any genus.

Description
Keywords
Citation