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.


closed as unclear what you're asking by Anton Menshov May 21 at 20:15

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 at 20:12
  • $\begingroup$ @LedHead good questions. Need some time for rethinking. $\endgroup$ – DaddyM Apr 30 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 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 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 at 20:15