<p>I will hang on the phrase "more specifically convex hulls" in your question title. The convex hull of $n$ points is a convex polyhedron and as such is completely specified by its vertices: two convex polyhedrons are congruent if and only if their vertex sets are congruent.</p>

<p>If the vertices are in the input, that version of your problem reduces to determining if two sets $A$ and $B$ of $n$ points each are congruent. A classical reference is <a href="http://www.springerlink.com/content/70001978171672p1/" rel="nofollow">this paper from 1988</a>, which achieves running time $\tilde{O}(n^{d-2})$. <a href="http://www.sciencedirect.com/science/article/pii/S0925772197000102" rel="nofollow">Akutsu</a> improves that to $O(n^{d/4 + O(1)})$ and shows that if $d$ is unbounded, then a polynomial time algorithm implies a polynomial time algorithm for graph isomorphism.</p>

<p>A <a href="http://portal.acm.org/citation.cfm?id=1314836" rel="nofollow">paper from 2008</a> looks at the parametrized complexity of the problem when one set is smaller than the other. This version of the problem is known as point set matching. Different approximate versions of the two problems have been widely studied (since the problems are motivated by computer vision, it's important for practice to have a robust version of congruence).</p>

<p>In case you have in mind a problem which does not reduce to congruence of point sets, please specify the full input to the problem.</p>

CC BY-SA 3.0
2011-06-21T19:37:53.110Z
Wrong problem — congruence ≠ rotation!  (See the OP's comment defining "same".)
Jeffε
CC BY-SA 3.0
2011-06-21T21:07:36.923Z
So he doesn't allow translations and reflections? That's arbitrary..are we sure that's what he means? It's probably bad practice to try to guess what an imprecise poster *really* is asking, but I would say the most "obvious" interpretation of "same" is congruence. @N27, can you clarify if you allow strictly only rotations..and if so, why?
Sasho Nikolov
CC BY-SA 3.0
2011-06-21T22:17:24.050Z
I think the answer from sasho is what i was waiting for. And yes I allow only rotations, not scaling. Thanks for your participation, though
N27
CC BY-SA 3.0
2011-06-21T22:26:09.910Z
And yes I should be more specific.
N27
CC BY-SA 3.0
2011-06-21T22:33:21.953Z
@N27: No, if my answer is what you're looking for, then you allow any rigid motion. This still excludes scaling, but is more than rotations.
Sasho Nikolov
CC BY-SA 3.0
2011-06-22T04:00:46.620Z
I was referring to the paper you indicated from Akutsu.
N27
CC BY-SA 3.0
2011-06-22T04:54:27.463Z
Ah, so you DO want congruences, and you're interested in point sets ? I have to say that while I'm glad you got the answer you wanted, this has relatively little to do with your original question
Suresh Venkat
CC BY-SA 3.0
2011-06-22T05:40:53.207Z
congruences=rotation, translation and/or reflection . A point set can be described giving vectors for the points. The points can then give a convex hull in the m-dimensional space, whose vertices are the points. Something similar is being done with the Goemans-Williamson algorithm for the Max-Cut problem, if you have studied it (they even have a picture of a 3-dimensional graph embedding, describing it as a convex hull embedded into the 3-dimensional sphere). So, the "relatively little" you mention is relatively far from reality.
N27
CC BY-SA 3.0
2011-06-22T17:07:36.887Z
@N27: I have to agree with Suresh, I am sorry. I only gave the answer you were looking for because I did not read your comments carefully and assumed what made most sense *to me*. In the future, you should consider being less abrasive and more precise. In the beginning you had only allowed rotations and that's that.
Sasho Nikolov
CC BY-SA 3.0
2011-06-21T18:02:31.693Z
2011-06-21T18:02:31.693Z
Sasho Nikolov
<p>Does anybody have information on whether the problem of determining whether 2 polyhedra in d dimensions are the same, is polynomial or NP-complete, if so?</p>

<p>Thanks</p>

CC BY-SA 3.0
2011-06-21T00:37:51.803Z
Is d a constant or a variable to you? I think it makes a difference here.
Jack
CC BY-SA 3.0
2011-06-21T00:48:29.533Z
it is a variable
N27
CC BY-SA 3.0
2011-06-21T02:31:25.377Z
how are the polyhedra given?
Sasho Nikolov
CC BY-SA 3.0
2011-06-21T02:50:30.313Z
as vectors in the d-dimensional space for the nodes and vectors again for the edges (between adjacent nodes)
N27
CC BY-SA 3.0
2011-06-21T03:37:03.403Z
And what does "same" mean"?  Be specific!
Jeffε
CC BY-SA 3.0
2011-06-21T03:39:24.103Z
Why do you need to specify the edges?  Why *don't* you need to specify the higher-dimensional faces?
Jeffε
CC BY-SA 3.0
2011-06-21T03:47:00.363Z
what does "same" mean? Obviously, it means that all vectors are equal upon a rotation in the d-dimensional space. What else could "same" mean? That we have one and only polyhedron. Specify what ever you want, I just want to know whether there is a research result on that.
N27
CC BY-SA 3.0
2011-06-21T07:06:14.890Z
Just rotation? Not scaling? There are a lot of notions of equivalence. It seems upon first glance that you're only interested in equivalence of 1-skeleta. Regardless, a Google search for "equivalence of polyhedra" turned up a lot of results.
Josephine Moeller
CC BY-SA 3.0
2011-06-21T16:59:30.267Z
@N27, it's your question that's not well defined. If you're comparing polyhedra, then your specification of the input in the comments doesn't make sense, as both JeffE and John point out. A polyhedron in d dimensions is more than just a collection of edges.
Suresh Venkat
CC BY-SA 3.0
2011-06-21T19:34:33.347Z
Your answer to my question is absolutely *not* "obvious".  You might mean that the face lattices are isomorphic (as lattices), or that the 1-skeletons are isomorphic (as graphs).  You might mean that one polyhedron is the image of the other under some geometric transformation (translation, rotation, reflection, glide reflection, screw motion, rigid motion, congruence, similarity, linear, affine, projective).  You might mean that the Hausdorff distance between the polytopes is below some threshold.  You might mean something else.  Different definitions can lead to *very* different answers!
Jeffε
<cg.comp-geom>
comparing polyhedra (or even more specifically convex hulls) in d dimensions
N27
# comparing polyhedra (or even more specifically convex hulls) in d dimensions

(Asked by: username_0 on 2011-06-21)

Does anybody have information on whether the problem of determining whether 2 polyhedra in d dimensions are the same, is polynomial or NP-complete, if so?

Thanks

**Tags:** cg.comp-geom
> **Comments:**
> **username_1**: Is d a constant or a variable to you? I think it makes a difference here.  
> **username_0**: it is a variable  
> **username_2**: how are the polyhedra given?  
> **username_0**: as vectors in the d-dimensional space for the nodes and vectors again for the edges (between adjacent nodes)  
> **username_3**: And what does "same" mean"?  Be specific!  
> **username_3**: Why do you need to specify the edges?  Why *don't* you need to specify the higher-dimensional faces?  
> **username_0**: what does "same" mean? Obviously, it means that all vectors are equal upon a rotation in the d-dimensional space. What else could "same" mean? That we have one and only polyhedron. Specify what ever you want, I just want to know whether there is a research result on that.  
> **username_4**: Just rotation? Not scaling? There are a lot of notions of equivalence. It seems upon first glance that you're only interested in equivalence of 1-skeleta. Regardless, a Google search for "equivalence of polyhedra" turned up a lot of results.  
> **username_5**: @N27, it's your question that's not well defined. If you're comparing polyhedra, then your specification of the input in the comments doesn't make sense, as both JeffE and John point out. A polyhedron in d dimensions is more than just a collection of edges.  
> **username_3**: Your answer to my question is absolutely *not* "obvious".  You might mean that the face lattices are isomorphic (as lattices), or that the 1-skeletons are isomorphic (as graphs).  You might mean that one polyhedron is the image of the other under some geometric transformation (translation, rotation, reflection, glide reflection, screw motion, rigid motion, congruence, similarity, linear, affine, projective).  You might mean that the Hausdorff distance between the polytopes is below some threshold.  You might mean something else.  Different definitions can lead to *very* different answers!  

---

## 1 answers

### Answer by username_2 on 2011-06-21. Score: 3 | Accepted answer

I will hang on the phrase "more specifically convex hulls" in your question title. The convex hull of $n$ points is a convex polyhedron and as such is completely specified by its vertices: two convex polyhedrons are congruent if and only if their vertex sets are congruent.

If the vertices are in the input, that version of your problem reduces to determining if two sets $A$ and $B$ of $n$ points each are congruent. A classical reference is [this paper from 1988](http://www.springerlink.com/content/70001978171672p1/), which achieves running time $\tilde{O}(n^{d-2})$. [Akutsu](http://www.sciencedirect.com/science/article/pii/S0925772197000102) improves that to $O(n^{d/4 + O(1)})$ and shows that if $d$ is unbounded, then a polynomial time algorithm implies a polynomial time algorithm for graph isomorphism.

A [paper from 2008](http://portal.acm.org/citation.cfm?id=1314836) looks at the parametrized complexity of the problem when one set is smaller than the other. This version of the problem is known as point set matching. Different approximate versions of the two problems have been widely studied (since the problems are motivated by computer vision, it's important for practice to have a robust version of congruence).

In case you have in mind a problem which does not reduce to congruence of point sets, please specify the full input to the problem.

> **Comments:**
> **username_3**: Wrong problem — congruence ≠ rotation!  (See the OP's comment defining "same".)  
> **username_2**: So he doesn't allow translations and reflections? That's arbitrary..are we sure that's what he means? It's probably bad practice to try to guess what an imprecise poster *really* is asking, but I would say the most "obvious" interpretation of "same" is congruence. @N27, can you clarify if you allow strictly only rotations..and if so, why?  
> **username_0**: I think the answer from sasho is what i was waiting for. And yes I allow only rotations, not scaling. Thanks for your participation, though  
> **username_0**: And yes I should be more specific.  
> **username_2**: @N27: No, if my answer is what you're looking for, then you allow any rigid motion. This still excludes scaling, but is more than rotations.  
> **username_0**: I was referring to the paper you indicated from Akutsu.  
> **username_5**: Ah, so you DO want congruences, and you're interested in point sets ? I have to say that while I'm glad you got the answer you wanted, this has relatively little to do with your original question  
> **username_0**: congruences=rotation, translation and/or reflection . A point set can be described giving vectors for the points. The points can then give a convex hull in the m-dimensional space, whose vertices are the points. Something similar is being done with the Goemans-Williamson algorithm for the Max-Cut problem, if you have studied it (they even have a picture of a 3-dimensional graph embedding, describing it as a convex hull embedded into the 3-dimensional sphere). So, the "relatively little" you mention is relatively far from reality.  
> **username_2**: @N27: I have to agree with Suresh, I am sorry. I only gave the answer you were looking for because I did not read your comments carefully and assumed what made most sense *to me*. In the future, you should consider being less abrasive and more precise. In the beginning you had only allowed rotations and that's that.  

---

