7

given an n*m matrix with the possible values of 1, 2 and null:

  . . . . . 1 . .
  . 1 . . . . . 1
  . . . 2 . . . .
  . . . . 2 . . .
  1 . . . . . 1 .
  . . . . . . . .
  . . 1 . . 2 . .
  2 . . . . . . 1

I am looking for all blocks B (containing all values between (x0,y0) and (x1,y1)) that:

  • contain at least one '1'
  • contain no '2'
  • are not a subset of a another block with the above properties

Example:

blocks

The red, green and blue area all contain an '1', no '2', and are not part of a larger area. There are of course more than 3 such blocks in this picture. I want to find all these blocks.

what would be a fast way to find all these areas?

I have a working brute-force solution, iterating over all possible rectangles, checking if they fulfill the first two criteria; then iterating over all found rectangles, removing all rectangles that are contained in another rectangle; and I can speed that up by first removing consecutive identical rows and columns. But I am fairly certain that there is a much faster way.

Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83
HugoRune
  • 13,157
  • 7
  • 69
  • 144
  • All edges of these blocks will be at the edge of the graph or adjacent to a "2". Perhaps you can do something with that. – robert Jun 12 '12 at 18:04
  • If you didn't get good answer here, you could also ask it in http://cs.stackexchange.com. – Saeed Amiri Jun 12 '12 at 18:21

3 Answers3

1

You can get somewhere between considering every rectangle, and a properly clever solution.

For example, starting at each 1 you could create a rectangle and gradually expand its edges outwards in 4 directions. Stop when you hit a 2, record this rectangle if (a) you've had to stop in all 4 directions, and (b) you haven't seen this rectangle before.

Then backtrack: you need to be able to generate both the red rectangle and the green rectangle starting from the 1 near the top left.

This algorithm has some pretty bad worst cases, though. An input consisting of all 1s springs to mind. So it does need to be combined with some other cleverness, or some constraints on the input.

Steve Jessop
  • 273,490
  • 39
  • 460
  • 699
  • This solution is a lot worse than the naive algorithm from the OP. – Thomash Jun 12 '12 at 18:23
  • @Thomash: it's not strictly worse, for example it's considerably faster than HugoRune's for any input with no `1`s in it. So the question is, I suppose, whether it's possible to identify cases where it's good, and use it conditionally. – Steve Jessop Jun 12 '12 at 18:24
  • Of course not, there are some specific cases where your algorithm is better. – Thomash Jun 12 '12 at 18:26
  • My instinct was that it could be made to work in cases where the vast proportion of the `N^2*M^2` possible rectangles have a `2` in them, or have no `1` in them. Its main quality is that it avoids considering those rectangles. And I think you can avoid growing the rectangle in the obviously-stupid way of recursing in all 4 directions, with vast numbers of duplicates because "left then right" is the same as "right then left". It may be that my instinct is wrong :-) – Steve Jessop Jun 12 '12 at 18:32
1

Consider the simpler one dimension problem:

Find all the substrings of .2.1.1...12....2..1.1..2.1..2 which contains at least one 1 and no 2 and are not substring of such string. This can be solved in linear time, you just have to check if there is a 1 between two 2.

Now you can easily adapt this algorithm to the two dimension problem:

For 1≤i≤j≤n sum all lines from i to j using the following law: .+.=., .+1=1, .+2=2, 1+1=1, 1+2=2, 2+2=2 and apply the one dimension algorithm to the resulting line.

Complexity: O(n²m).

Thomash
  • 6,339
  • 1
  • 30
  • 50
  • Thanks for the suggestion. I am not sure, but I think this is O(n³m), since for a given i and j it is already O(nm). Still most likely faster than brute force though. – HugoRune Jun 12 '12 at 22:21
  • @HugoRune No, for a given i and j, it is O(m) because it is the one dimension problem. You may say it is O(nm) because you have to compute the "sum" from i to j but this is actually not the case since you can reuse the result for i, j-1. – Thomash Jun 12 '12 at 23:01
1

I finally found a solution that works almost in linear time (there is a small factor depending on the number of found areas). I think this is the fastest possible solution.

Inspired by this answer: https://stackoverflow.com/a/7353193/145999 (pictures also taken from there)

First, I go trought the matrix by column, creating a new matrix M1 measuring the number of steps to the last '1' and a matrix M2 measuring the number of steps to the last '2' M1 & M2

imagine a '1' or '2' in any of the grey blocks in the above picture

in the end I have M1 and M2 looking like this:

enter image description here

No go through M1 and M2 in reverse, by row:

enter image description here

I execute the following algorithm:

 foundAreas = new list()

 For each row y backwards:
     potentialAreas = new List()
     for each column x:
        if M2[x,y]>M2[x-1,y]:
            add to potentialAreas: 
                new Area(left=x,height=M2[x,y],hasOne=M1[x,y],hasTop=false)
        if M2[x,y]<M2[x-1,y]:
            for each area in potentialAreas:
                 if area.hasTop and area.hasOne<area.height:
                        add to foundAreas:
                             new Box(Area.left,y-area.height,x,y)
            if M2[x,y]==0: delete all potentialAreas
            else:
                 find the area in potentialAreas with height=M2[x,y] 
                 or the one with the closest bigger height: set its height to M2[x,y]
                 delete all potentialAreas with a bigger height

            for each area in potentialAreas:
                 if area.hasOne>M1[x,y]: area.hasOne=M1[x,y]
                 if M2[x,y+1]==0: area.hasTop=true

now foundAreas contains all rectangles with the desired properties.

Community
  • 1
  • 1
HugoRune
  • 13,157
  • 7
  • 69
  • 144