Representing Polyhedra: Faces are Better than Vertices

dc.contributor.authorHeath, Lenwood S.en
dc.contributor.authorParipati, Praveen K.en
dc.contributor.authorRoach, John W.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2013-06-19T14:36:21Zen
dc.date.available2013-06-19T14:36:21Zen
dc.date.issued1990en
dc.description.abstractIn 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.en
dc.format.mimetypeapplication/pdfen
dc.identifierhttp://eprints.cs.vt.edu/archive/00000246/en
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000246/01/TR-90-64.pdfen
dc.identifier.trnumberTR-90-64en
dc.identifier.urihttp://hdl.handle.net/10919/19692en
dc.language.isoenen
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen
dc.relation.ispartofHistorical Collection(Till Dec 2001)en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.titleRepresenting Polyhedra: Faces are Better than Verticesen
dc.typeTechnical reporten
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
TR-90-64.pdf
Size:
1.57 MB
Format:
Adobe Portable Document Format