Timeline for Maximum coverage of an orthogonal polygon using $k$ rectangles
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 25 at 14:30 | comment | added | Joseph O'Rourke | You might look at this for ideas when $k=2$: Bespamyatnikh, Sergei. "Packing two disks in a polygon." Computational Geometry 23, no. 1 (2002): 31-42. | |
| Aug 25 at 11:55 | comment | added | Joseph O'Rourke | Each edge of a maximal rectangle $R$ must be flush with (pushing against) an edge of the polygon. Otherwise it could be expanded. So that accords with your $O(n^4)$. And if you select top and bottom polygon edges for $R$, then either $R$ goes exterior, or left/right edges of $R$ are determined. So this improves on brute force. | |
| Aug 25 at 1:59 | comment | added | user536106 | For k = 1, we can solve in polynomial time via brute-force search. If I assume that my orthogonal convex polygon takes up at most $n$ horizontal units and $n$ vertical units, then a single rectangle is defined by an interval on the x axis and an interval on the y axis. There are $O(n^2)$ such intervals on the x axis and $O(n^2)$ on the y axis, for a total $O(n^4)$ runtime. I'm pretty sure the exponent can be reduced by being a little smarter with pruning intervals. | |
| Aug 25 at 1:53 | comment | added | user536106 | Yes, the rectangles should be inscribed in the polygon. Every edge of the polygon and every edge of the k rectangles should be either horizontal or vertical. | |
| Aug 24 at 23:02 | comment | added | Joseph O'Rourke | For $k=1$, perhaps a variant of this would work: Alt, Helmut, David Hsu, and Jack Snoeyink. "Computing the largest inscribed isothetic rectangle." In CCCG, pp. 67-72. 1995. See also this useful student project. | |
| Aug 24 at 23:01 | comment | added | Joseph O'Rourke | Presumably you want your rectangles to be inside the polygon. Should the rectangles be "isothetic," oriented the same as the edges of the polygon? | |
| Aug 24 at 6:22 | history | edited | Daniele Tampieri | CC BY-SA 4.0 |
Stated precise reference
|
| S Aug 24 at 4:26 | review | First questions | |||
| Aug 24 at 6:22 | |||||
| S Aug 24 at 4:26 | history | asked | user536106 | CC BY-SA 4.0 |