2
$\begingroup$

I have an orthogonal polygon (all edges are horizontal or vertical) which is convex (no holes in any row of column of the polygon).

I would like to cover as much as possible of this orthogonal polygon using at most $k$ rectangles.

I know the minimum cover version of this problem has been extensively studied, e.g. by Deborah S. Franzblau and Daniel J. Kleitman in their paper "An algorithm for constructing regions with rectangles: Independence and minimum generating sets for collections of intervals", Proceedings of the sixteenth annual ACM symposium on Theory of computing (STOC '84). Association for Computing Machinery, New York, NY, USA, 167–174, DOI:10.1145/800057.808678 (1984).

However, I am struggling to find results that extend to the maximum coverage version, i.e., instead of covering the whole polygon with as few rectangles as possible, I want to cover as much of the polygon as possible knowing I can only use $k$ rectangles.

Any leads?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Presumably you want your rectangles to be inside the polygon. Should the rectangles be "isothetic," oriented the same as the edges of the polygon? $\endgroup$
    – Joseph O'Rourke
    Commented Aug 24 at 23:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joseph O'Rourke
    Commented Aug 24 at 23:02
  • $\begingroup$ 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. $\endgroup$
    – user536106
    Commented Aug 25 at 1:53
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joseph O'Rourke
    Commented Aug 25 at 11:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joseph O'Rourke
    Commented Aug 25 at 14:30

0

Reset to default

You must log in to answer this question.