Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

We have two Polygons/Polyhedra P and Q.

Does there exist a polynomial time algorithm to decide if we can put P (using translation and rotation) inside Q or not?

First think about the case of which P and Q are convex and the input is the list of vertices, edges and faces of P,Q.

share|improve this question
1  
Since you're asking about computational complexity, you should indicate how the inputs, P and Q, are given. A convex polyhedron could be given by a list of its vertices, or by a list of linear inequalities. There is no polynomial-time way to convert one of these to the other (because either one can be exponentially longer than the other), so an algorithm that runs in polynomial time with one presentation of the input need not give a polynomial-time algorithm for the other presentation. –  Andreas Blass Aug 2 at 15:52
    
Thanks, edited. First think about the case of which the input is the list of vertices, edges and faces. Because we cant uniquely determine a polyhedron with only its vertices. –  Morteza Aug 2 at 16:36
1  
I just want to point out that the title can be read "put P inside Q factorial polygons/polyhedra" and that reading is quite confusing... –  Qiaochu Yuan Aug 4 at 4:30

2 Answers 2

To make sense of this question one has to say first what you mean by "copy of $P$". For example one could image to allow translations, rigid motions and/or dilations.

The answer also depends on how the the (convex) polytopes are given.

There is some literature on this topic, a starting point could be:

Peter Gritzmann and Victor Klee. On the complexity of some basic problems in computational convexity: I. containment problems. Discrete Mathematics, 136(1):129–174, 1994.

From this paper: enter image description here

This Theorem does not consider a "copy of $P$" but only $P$ itself, other cases lead to cases that don't have a polynomial time algorithm.

For the polygon-case a good reference might be:

Bernard Chazelle. The polygon containment problem. In Franco P. Preparata, editor, Advances in Computing Research I, pages 1–33. JAI Press, 1983.


Edit: after your clarification let my restate the question:

Given two $\mathcal{V}$-polytopes $P$ and $Q$, is there a polynomial time algorithm to find a $\mathcal{V}$-polytope $P'$ such that $P'\subset Q$ and $P'$ can be transformed into $P$ by rigid motions?

The answer to this question is: No

The relevant section of the first reference above is Section 7. Optimal containment under similarity and related questions.

As mentioned there, this question is already difficult if $Q$ is a cube. Note the they look at the closely related question of finding a copy of $Q$ that contains $P$. (Instead of "contains $P$" we can simply ask for "covers the vertices of $P$", if convexity is assumed)

share|improve this answer
    
"and/or dilations" - well, obviously not those, or we could just shrink P to fit. –  user2357112 Aug 2 at 18:12
    
@user2357112 you are right. "dilations" start to make sense when you ask for "the largest copy of $P$" –  Moritz Firsching Aug 2 at 20:25
    
Thanks, edited. I mean P itself using translation and rotation. –  Morteza Aug 2 at 23:02

There is quite a bit of literature specifically on polygon containment, much of deriving from robotics applications. The paper below solves the containment problem, allowing translations and rotations, with a polynomial-time algorithm (roughly $O(n^6)$).

Avnaim, Francis, and Jean Daniel Boissonnat. "Polygon placement under translation and rotation." Informatique theorique et applications. 23(1). 1989. p.5-28.

Here is a snapshot from their introduction. The two polygons, named $E$ and $I$, have $n$ and $m$ edges respectively. This Intro reviews related, prior work:


      Intro
Their algorithm extends to handle the case of polyhedra in $\mathbb{R}^3$, but for translation only (no rotation).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.