1
$\begingroup$

I have a polyhedron and want to determine whether it is combinatorially equivalent to another polyhedron. I know how many faces comprise each polyhedron and for each face, I know all of its vertices, and for each vertex, I know its location.

For example, if I had a pentahedron, I would want to figure out whether it was a triangular prism or a square pyramid. I can easily do this for pentahedral, but do not know how to do it for arbitrary polyhedra.

Additionally, if two polyhedra are the the same shape, I want to map the vertices from one to the other.

Can anyone point me to an algorithm to accomplish these things?

  • 0
    So is this like the polyhedron version of [graph isomorphism](http://en.wikipedia.org/wiki/Graph_isomorphism)?2012-02-28

1 Answers 1

1

As J.D. has pointed out in a comment, this is a special case of the graph isomorphism problem. No polynomial-time algorithm is known for the general case, but there are special-purpose algorithms for planar graphs, polyhedral graphs (graphs of convex polyhedra) and graphs of general polyhedra. The introduction to this paper contains a useful collection of references, including one to this paper, which takes a practical point of view and finds that the linear-time algorithm for planar graphs is only more efficient than state-of-the-art general-purpose graph isomorphism algorithms if there are about $1000$ vertices or more. This is typical for the graph isomorphism problem, which is quite easy to solve in most cases but has peculiar theoretical properties.

  • 0
    Thanks! That was a key understanding I was missing, and it helped me look the right places for the rest of what I'm looking for.2012-03-01