1
$\begingroup$

As an example of the type of problem, consider Stewart Coffin's Cruiser puzzle:

Let R be a 48 × 31 rectangle. Let T be a 30°-60°-90° triangle with hypotenuse 34.565 (so legs are 17.2825 and 29.934). Let P be a right trapezoid with base 20.0982 and altitudes 27.1178 and 15.514. Show how to place two copies of T and two copies of P inside R with no overlap.

Pieces for the cruiser puzzle

Solution

The algorithm should be able to solve for any number of polygons of any shape within another polygon of any shape (or conclude that such a solution is not possible).

$\endgroup$
1
$\begingroup$

Tiling figures of the plane with two bars shows that this problem is NP-complete in the general case. Simply have the horizontal and vertical bar the same size $\geq 3$.

$\endgroup$
  • $\begingroup$ What does "greater than 3" mean? $\endgroup$ – WHY Sep 22 '18 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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