11

Simplified, I have to solve the following problem:

You have a 2-dimensional array filled with 0s and 1s. Find the minimum number of rectangles such that they cover all 1s. Rectangles should not overlap.

The function signature might look like: List<Rectangle> FindCoveringRectangles(bool[,] array)

I already have a solution that is "good enough" but doesn't always find the minimum number of rectangles. I'd like to know if there is some well known and efficient algorithm that can be applied to solve this problem?

Example:

An input array of:

..........
.1.....11.
.......11.
...111....
...111....
...111....
....1111..
....1111..
......11..
..........

(0s replaced by dots for readability)

Might result in the following rectangles:

(2,2,2,2),
(2,8,3,9),
(4,4,6,6),
(7,5,8,8),
(9,7,9,8)

(top, left, bottom, right), 1-based

There can be more than one solution, but one is enough.

Mike Nakis
  • 56,297
  • 11
  • 110
  • 142
stmax
  • 6,506
  • 4
  • 28
  • 45
  • If you tell us your approximation algorithm, perhaps we can help improve it in the worst case. – Thomas Ahle Dec 26 '11 at 22:59
  • 1
    What are you trying to optimize? The minimum number of rectangles is always 1. – ThomasMcLeod Dec 26 '11 at 23:10
  • This problem is solved excellently in the context of [Karnaugh maps](http://en.wikipedia.org/wiki/Karnaugh_map). – thiton Dec 26 '11 at 23:16
  • @thiton: Karnaugh maps are only 4x4 in two dimensions, and they wrap. I don't think it's quite clear how to use their usual exponential time algorithm to create a polynomial time solution for this problem. – Thomas Ahle Dec 26 '11 at 23:22
  • Can someone explain why one rectangle cannot cover any array? – ThomasMcLeod Dec 26 '11 at 23:48
  • 1
    @ThomasAhle: Karnaugh maps get higher-dimensional (8x8, 16x16 and more) with more variables. While the exact Quine-McCluskey method is NP-hard, the Espresso heuristic should give good results. I can't give full details due to limited knowledge of the topic, but I know that Karnaugh maps are widely used and are very similar to the topic at hand. – thiton Dec 27 '11 at 18:43
  • 1
    @ThomasMcLeod: You are to cover the ones only. – Thomas Ahle Dec 27 '11 at 18:50
  • Thanks for all comments so far! @Thomas Ahle: the current algorithm picks a 1 that hasn't been visited yet, extends the rectangle from there to the left/right/up/down, marks the covered 1s as visited and repeats these steps until all 1s are covered. – stmax Dec 27 '11 at 22:12
  • @thiton: thanks for the suggestion - will have a look at the Espresso heuristic. – stmax Dec 27 '11 at 22:15
  • @stmax: Just for the sake of the analysis, do you extend first vertically or first horizontally? – Thomas Ahle Dec 27 '11 at 22:23
  • @ThomasAhle i'm not sure about the exact direction since a coworker implemented the algorithm and we're still on vacation / can't check the source right now. we were talking about first horizontally, then vertically, but i'm not sure if that made it into the actual implementation. do you think it'd make a difference? – stmax Dec 30 '11 at 23:32
  • Probably not. I think your algorithm runs `O(n^2)` with `n` being the area of the array. A bad case would be the checkerboard pattern, as you likely restart the scan every time a rectangle has been added. This means that even the slowest and simplest 1984 approach would be worth considering. – Thomas Ahle Dec 31 '11 at 00:13
  • Related: http://math.stackexchange.com/questions/1020550/minimal-number-of-rectangles-that-cover-a-set-of-adjacent-unit-squares | http://cstheory.stackexchange.com/questions/16541/fitting-minimum-number-of-rectangles-of-width-height-1-into-a-2d-grid | http://softwareengineering.stackexchange.com/questions/328669/covering-a-grid-with-minimal-number-of-rectangles – Ciro Santilli OurBigBook.com Feb 19 '17 at 15:10

1 Answers1

7

This is a matching problem of a kind, that could easily have shown NP-hard. However it seems there is actually a very fast solution!

Using a bfs flood-fill you can find each connected component, O(n). Hence wlog we can assume that we just have to fill one connected area.

If the area doesn't have holes in it, you can use the algorithm described in this paper (or here on google scholar.)

An O(n log log n) algorithm is proposed for minimally rectangular partitioning a simple rectilinear polygon. For any simple rectilinear polygon P, a vertex-edge visible pair is a vertex and an edge that can be connected by a horizontal or vertical line segment that lies entirely inside P. It is shown that, if the vertex-edge visible pairs are found, the maximum matching and the maximum independent set of the bipartite graph derived from the chords of a simple rectilinear polygon can be found in linear time without constructing the bipartite graph. Using this algorithm, the minimum partition problem for convex rectilinear polygons and vertically (horizontally) convex rectilinear polygons can be solved in O(n) time

Some of the papers referred to also cover the case of an area with holes. These run in O(n^(3/2)logn) though, but they still seam pretty good.

Alternatively, one thing you might do is solving the problem without holes, solving the problem for each hole, and then subtract. This might not give an optimal solution though, but would keep the runtime.

You could also try and split the shape in its different topological parts, but that would likely run exponentially in the number of holes.

Thirdly you could try to adapt the proposed algorithm for the more general case, but it might be hard.

Thomas Ahle
  • 30,774
  • 21
  • 92
  • 114
  • thanks, the abstract sounds promising. will have to wait till i'm back at work until i can download the whole article though :( – stmax Dec 27 '11 at 22:42
  • 1
    Yes, unfortunately I didn't find the paper anywhere else. - This is the simpler but O(n^2) original approach: http://www.sciencedirect.com/science/article/pii/0734189X84901397 - This is the hole-supporting O(n^3/2logn) approach: http://epubs.siam.org/sicomp/resource/1/smjcat/v15/i2/p478_s1 – Thomas Ahle Dec 27 '11 at 23:49
  • The techniques all somehow split the polygon in horizontal and vertical parts. These are put into a graph connected to their intersections. The graph turns out to be bipartite, and hence we can find a "maximum independent set" fast. (O(n^2) with a stock algorithm). – Thomas Ahle Dec 27 '11 at 23:52
  • This presentation has somewhat of a walk through: http://www.math.unl.edu/~s-dstolee1/Presentations/Sto08-MinRectPart.pdf – Thomas Ahle Dec 27 '11 at 23:52
  • thanks for the additional links. i already found the last one a few days ago when i searched for a free copy of the first paper. not very detailed, but at least it extended my vocabulary by giving me names / definitions for a few things. :) – stmax Dec 30 '11 at 23:24
  • The IEEE link in the answer is broken. – letmaik Mar 31 '16 at 16:59
  • Thanks, I've fixed the link. – Thomas Ahle Mar 31 '16 at 18:32