1
$\begingroup$

I have a curve on a plane, and a rectangle with one side much longer than the other (let's say it is a "thick segment). I need to find a set of positions of the rectangle which would include all the points of the curve. Overlaps of the rectangle positions are allowed. Possibly I would need to optimize the problem, finding the minimal set. But a good algorithm for the complete covering would be a good start.

Here is a sketch:

sketch

This is the 2D version of this 3D problem.

Improve this question
$\endgroup$
7
  • $\begingroup$ Are the sides of the rectangle fixed beforehand? $\endgroup$
    – nicoguaro ♦
    Commented Dec 28, 2023 at 15:11
  • 2
    $\begingroup$ greedy algorithm could be a start, each rectangle covers as much as possible one after another. The sub-problem should be much easier to solve. $\endgroup$
    – Yimin
    Commented Dec 28, 2023 at 21:44
  • $\begingroup$ nicoguaro no, the sides are free to be put in any position $\endgroup$
    – Fabio
    Commented Dec 29, 2023 at 9:43
  • $\begingroup$ @Yimin good idea, thank you! $\endgroup$
    – Fabio
    Commented Dec 29, 2023 at 9:53
  • 2
    $\begingroup$ Welcome to Scicomp. What is the tradeoff / penalty for using larger rectangles. With the information you have given, a single giant rectangle will do the job. $\endgroup$
    – MPIchael
    Commented Jan 3 at 8:14

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.