12
$\begingroup$

I am trying to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle.

I thought about trying to decompose my concave polygon into triangles that produce a set of minimally overlapping rectangles minimally bounding each triangle and then merging those rectangles into larger ones. However, I don't think this will work for small notches in the edges of the polygon. The triangles created by the reflex vertices on those notches will create the wrong rectangles. I am looking for rectangles that will span/ignore notches.

I don't really know anything about computational geometry, so I'm not really sure on how to begin asking the question.

I found other posts that were similar, but not what I need:

Some examples: Black is the input. Red is the acceptable output.

enter image description here

Another example: The second output is preferred. However, generating both outputs and using another factor to determine preference is probably necessary and not the responsibility of this algorithm.

enter image description here

enter image description here

Polygons that mimic curves are extremely rare. In this scenario much of the area of the rectangles is wasted. However, this is acceptable because each rectangle obeys the max width constraint.

enter image description here

Also, I found this article to be close to what I need:

Maybe a better question is "How can I identify rectangular-like portions of a concave polygon?" enter image description here

Here is an image showing the desired implementation: enter image description here

The green is the actual material usage. The red rectangles are the layouts. The blue is the MBR of the entire polygon. I am thinking I should try to get little MBRs and fill them in. The 2-3 green rectangles in the upper left corner that terminate into the middle of the polygon are expensive. That is what I want to minimize. The green rectangles have a min and max width and height, but I can use as many rows and columns necessary to cover a region. Again, I must minimize the number of rectangles that do not span across the input. I can also modify the shape of the green rectangle to fit in small places that is also very expensive. In other words, getting as many rectangles as possible to span as much as possible is ideal.

$\endgroup$
5
  • 1
    $\begingroup$ What is a concave polygon? $\endgroup$
    – Igor Rivin
    Aug 21, 2012 at 15:26
  • $\begingroup$ And how does "concave" in the first sentence become "convex" in the third, yet still allow "notches" in the fourth? $\endgroup$ Aug 21, 2012 at 17:43
  • $\begingroup$ @Andreas Blass Oops. I meant concave everywhere. Thank you for the correction. $\endgroup$
    – Josh C.
    Aug 21, 2012 at 18:43
  • $\begingroup$ Also posted at StackOverflow: stackoverflow.com/questions/12059680 $\endgroup$ Aug 21, 2012 at 18:58
  • $\begingroup$ Cross-posted: cstheory.stackexchange.com/q/12376/5038 $\endgroup$
    – D.W.
    Mar 20, 2023 at 6:23

2 Answers 2

8
$\begingroup$

Here is one relevant result, by Michael Hoffmann, "Covering polygons with few rectangles," 2001. (PDF download link)
        Hoffmann Italy
He shows that minimal covering by two or three congruent axis-aligned rectangles of a collection of polygons with a total of $n$ vertices can be found in $O(n)$ time.

He also says that the more general problem—covering a set of polygons by $p>3$ congruent rectangles—cannot be approximated by better than a factor of $2$ unless $P=NP$ (because of the relation to the $p$-center problem). He does not directly address covering just one polygon, or with covering by incongruent rectangles.

This latter problem (your problem) is partially addressed computationally in the paper 2011, "Covering a polygonal region by rectangles," Computational Optimization and Applications (Springer link). It appears that they start with a set of rectangles, and extend them until they form a cover.

$\endgroup$
6
  • $\begingroup$ Is there a difference between minimal and few? If not, I'll have to determine k. If so, I guess I need to define minimal. $\endgroup$
    – Josh C.
    Aug 21, 2012 at 19:23
  • $\begingroup$ I think for my problem more rectangles are acceptable so long as an edge of the rectangle is shared with an edge of the polygon (or is at least parallel). In other words, a tigher fit of rectangles with minimum overlap is important. I found this: emis.de/journals/ASUO/mathematics/pdf6/… My problem is similar to the principle of laying carpet. However, I don't have the luxury of cutting a small piece to fill a small remaining area. $\endgroup$
    – Josh C.
    Aug 21, 2012 at 19:30
  • $\begingroup$ Also, congruence isn't important. $\endgroup$
    – Josh C.
    Aug 22, 2012 at 16:08
  • $\begingroup$ @Josh: Yes, I understand that congruence is not important to you. The 1st paper I cited was emphasizing creating maps, for which the congruency condition makes sense. This is not a direct hit to your concerns. $\endgroup$ Aug 22, 2012 at 16:49
  • $\begingroup$ I reposted my question in the theoretical comp sci stack exchange. I've gone into more detail there. (I'm not trying to spam my question around. I'm just not quite sure where to post it, and I read the faqs to make sure I wasn't doing something wrong) cstheory.stackexchange.com/questions/12376/… Do you think this answer still works with some of the other information I've given. I may have simply misstated my problem. $\endgroup$
    – Josh C.
    Aug 22, 2012 at 22:12
1
$\begingroup$

See

A Linear-Time Approximation Algorithm for Minimum Rectangular Covering by by Christos Levcopoulos , Joachim Gudmundsson

They consider what seems to be exactly your problem (and citeseer seems to have the pdf available).

$\endgroup$
2
  • $\begingroup$ My rectangles do not have to lie entirely within the rectangle. I added a link with some images in the post to help explain: imgur.com/Qowx2 Also, googling on your description of the problem, I did find something a bit closer to what I need: emis.de/journals/ASUO/mathematics/pdf6/… $\endgroup$
    – Josh C.
    Aug 21, 2012 at 16:51
  • $\begingroup$ My rectangles do not have to lie entirely within the *polygon. $\endgroup$
    – Josh C.
    Aug 21, 2012 at 17:03

Your Answer

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

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