Skip to main content
MathOverflow

Return to Question

Stated precise reference
Source Link
Daniele Tampieri
Daniele Tampieri
  • 6.4k
  • 7
  • 30
  • 45

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 https://dl.acm.org/doi/pdf/10.1145/800057.808678(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?

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. https://dl.acm.org/doi/pdf/10.1145/800057.808678

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?

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?

Source Link
user536106
user536106
  • 21
  • 1

Maximum coverage of an orthogonal polygon using $k$ rectangles

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. https://dl.acm.org/doi/pdf/10.1145/800057.808678

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?