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?

$\endgroup$
1
  • $\begingroup$ So is this like the polyhedron version of graph isomorphism? $\endgroup$
    – user2468
    Feb 28, 2012 at 4:47

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Mike Graham
    Mar 1, 2012 at 21:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .