2
$\begingroup$

I am solving the task that is as follows:

Input: a polygon. Can be any kind of polygon without self intersections. Can be a non-convex and with holes inside.

Goal: to cover it with 2 (at least) or more parallelograms that together are equal to or contain the whole polygon. The following criteria should be met:

  • There is no point of the polygon that lies beyond parallelograms.
  • The number of the parallelograms should be the least possible. I.e. we want to find largest parallelograms that cover the polygon.
  • These parallelograms must not intersect within the polygon.

Question: Is this task solved and if it is solved - how? I am looking for a direction where to start with and what related algorithms/theory to learn.

$\endgroup$
  • 5
    $\begingroup$ I think your problem description is missing something. (1) Why does it have to be two or more parallelograms? If my input polygon is itself a parallelogram, why can't i just use that parallelogram as the solution? (2) You state that your parallelograms can "contain the whole polygon". A single square that's big enough solves that. $\endgroup$ – LedHead Apr 28 '19 at 20:12
  • $\begingroup$ @LedHead good questions. Need some time for rethinking. $\endgroup$ – DaddyM Apr 30 '19 at 7:48
  • 1
    $\begingroup$ Interesting problem! Could you provide one or two sketches of what is a correct solution and which not? Or one optimal and one sub-obtimal solution? $\endgroup$ – MPIchael Apr 30 '19 at 12:25
  • $\begingroup$ @MPIchael hey thanks! I am currently working on the task deeper specification. I will come back with images within few days. $\endgroup$ – DaddyM Apr 30 '19 at 13:35
  • $\begingroup$ I closed this question for now, until the clarifications arrive – and to attract the attention of @DaddyM. I would be happy to reopen it. $\endgroup$ – Anton Menshov May 21 '19 at 20:15