5
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 2, 2014 at 15:52
  • $\begingroup$ 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. $\endgroup$
    – Morteza
    Aug 2, 2014 at 16:36
  • 1
    $\begingroup$ 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... $\endgroup$ Aug 4, 2014 at 4:30

2 Answers 2

9
$\begingroup$

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)

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

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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