Flipping objects in a bounded region

Shape and space, angle and circle properties, ...
Post Reply
Bubbler
Posts: 28
Joined: Sat Feb 23, 2013 6:12 am

Flipping objects in a bounded region

Post by Bubbler » Mon Feb 23, 2015 12:03 pm

(Sorry, this problem is kind of computational geometry, not math-oriented...)

A convex polygonal region R with k vertices is given on a 2D plane, and there are n convex polygons Pi, with k vertices each, which are pairwise disjoint and completely inside R. These polygons do not sum to R; in other words, there are some gaps inside R that are not part of any of Pi.

Now you want to flip each Pi - place the mirror image Pi' of Pi so that the position of its center of mass remains constant. Each Pi' must still lie inside R and be pairwise disjoint. Rotation of Pi' around the center of mass is freely allowed.

Is it possible to computationally determine whether each polygon can be successfully flipped or not?
Image

User avatar
jaap
Posts: 528
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Flipping objects in a bounded region

Post by jaap » Mon Feb 23, 2015 3:00 pm

I don't doubt that it can be done, but it will be very difficult. You will have to reduce it to a combinatorial problem.
That means that the n degrees of freedom, which are the mirror angles for the n pieces, each have to be restricted to a finite set of values in such a way that a solution is present whenever the original problem has a solution.

However even if this reduction can be done, it may be the case that this class of combinatorial problem is difficult. It would not surprise me if it is a PSPACE-complete problem, even if all the pieces are only allowed to be mirrored vertically or horizontally.
I have written a page about PSPACE completeness for a different kind of puzzle here: http://www.jaapsch.net/puzzles/pspace.htm
It feels to me that there will probably be a way to define wires, AND and OR widgets, etcetera using only horizontal/vertical mirroring of pieces. If that is the case, then it means that if you were to actually find a program that can solve it quickly (in polynomial time) then you will win a million dollars.

Post Reply