Dynamic programming: finding largest triangle

Question

I need to find the largest triangle of ones in a matrix of zeros and ones using dynamic programming. So if this is my matrix:

 1 0 0 1 1
 0 1 1 1 1
 0 1 1 1 0
 1 1 1 1 1
 1 1 0 0 1

Then there are two largest triangles with the right corner at [2,2] and [4,4]. I only have to look for the right isosceles triangles (which have the angles 90◦, 45◦, 45◦) and I also need to look at only one orientation, because all the others are symmetric. So basically I need a function which takes the matrix and returns a triangle, with triangle being an object. I don't need complete code pseudocode is fine too me.

First I thought of just using the square algorithm here: Dynamic programming - Largest square block, and when you have found the largest square, then the largest triangle must be in there. But I can easy find counter examples where this doesn't work. After that I tried to look at the upper cell and counting this with dynamic programming, but I am not sure what to do next... So my count will look like this with the matrix from above:

1 0 0 1 1
0 1 1 2 2
0 2 2 3 0
1 3 3 4 1
2 4 0 0 2

I think have to use this in some way.

UPDATE:

I think I am pretty close now, when you walkthrough the matrix n*m and and make count[i][j] = 1+ min(count[i-1][j], count[i][j-1]), so look at the left and upper cell. We get this:

1 0 0 1 1
0 1 1 2 2
0 1 2 3 0
1 2 3 4 1
1 2 0 0 1

This looks pretty good to me, you can the see where the right corner is of the [4,4] solution. Can anyone think of any counter examples? I only I have to return one solution, so returning this solution is fine.

UPDATE 2: I have found a counterexample, let position [4,4] be 0, we then get the following matrix:

 1 0 0 1 1
 0 1 1 1 1
 0 1 1 1 0
 1 1 1 0 1
 1 1 0 0 1

Count will look like this after walking through the matrix:

1 0 0 1 1
0 1 1 2 2
0 1 2 3 0
1 2 3 0 1
1 2 0 0 1

Now it will return the triangle with right corner [3,4] (third row fourth column), which is incorrect it should find [2,2]. So I thought maybe just going from the top left (what we have done so far) and from the right bottom and take the max from that. So count with right bottom will look like this (look at the cell below and to the right):

1 0 0 2 1
0 4 3 2 1
0 3 2 1 0
2 2 1 1 1
1 1 0 0 1

Now we do find the solution of [2,2]. So I think using these methods will give me the solution, can anyone think of a better solution or a counter example for this one?

UPDATE 3: kraskevich made me realize that we have to use this algorithm four times. From the top left, top right, bottom left, bottom right and then just take the maximum, because then you have taken all the possibilities. Anyone has a better way to do this? Is this algorithm then correct? (So just four times the same algorithm, only an other start point in the matrix)

Also for the people who don't really understand what I am doing (I might go a little fast) take a look again at this: Dynamic programming - Largest square block the approach is very similar and it is very well explained there what there is done.

Answer 1

Yes, your idea is almost correct. Let's formalize it.

Claim:

f(i, j) is the size of the largest triangle with the right bottom corner at the (i, j) position and it is computed correctly.

Proof:

Let's use induction.

The base case: for all cells in the first row and or in the first column the size of a triangle is either one or zero(depending on the value in this cell).

Induction step:

Let's assume that f(i - 1, j) and f(i, j - 1) have been computed correctly.

1. f(i - 1, j) >= f(i, j) - 1 and f(i, j - 1) >= f(i, j) - 1.It is the case because any sub-triangle of a triangle with 1s is a triangle with 1s. It implies that f(i, j) <= f(i - 1, j) + 1 and f(i, j) <= f(i, j - 1) + 1, or, put it another way, f(i, j) <= min(f(i - 1, j) + 1, f(i, j - 1) + 1) = min(f(i - 1, j), f(i, j - 1)) + 1. Thus, f(i, j) <= min(f(i - 1, j), f(i, j - 1)) + 1 holds true.

2. Let's assume that min(f(i - 1, j), f(i, j - 1)) = k. Then there is triangle of size k in the (i - 1, j) cell and another triangle of size k in the (i, j - 1) cell. Together with the (i, j) cell, these two triangles form a triangle of size k + 1. Thus, f(i, j) >= min(f(i - 1, j), f(i, j - 1)) + 1.

I have just shown that f(i, j) >= min(f(i - 1, j), f(i, j - 1)) + 1 and f(i, j) <= min(f(i - 1, j), f(i, j - 1)) + 1. It implies that f(i, j) = min(f(i - 1, j), f(i, j - 1)) + 1. Thus f(i, j) is computed correctly, too.

Note that we have taken into account only such triangles that have their right angle in the right-bottom position. To take into account all possible triangles, we can simply run this algorithm for all 4 possible rotations of the given matrix.

Let's prove that running this algorithm in 4 directions is sufficient:

There are only four possible positions of the right angle of an arbitrary right isosceles triangle in a matrix: bottom-left, bottom-right, top-left and top-right. Running this algorithm in a fixed direction finds the largest triangle for this direction(I have proven it above). Thus, running this algorithm in all possible direction is sufficient to find the largest triangle in the matrix.

This algorithm is optimal in terms of time complexity because it has an O(n * m) time complexity, and just reading the input already requires O(n * m) time(we cannot find the answer without seeing all elements of the matrix in a general case).

Answer 2

Disclaimer:

I did not merely restate what the OP is doing, in fact, the way we are updating the count is different.

I agreed with @IVlad that I should elaborate more on why the algorithm stated in my solution works, so I have edited my answer to include the key idea (the observation part) of the approach I wrote.

At the time I posted my solution, I am completely unaware of the OP's approach (see the revision history for evidence, the third revision was made by me), so actually I did not even attempt to restate what the OP was doing. I was just hoping to give a formalised description of an approach for the problem.

Originally I have been trying to avoid posting formal mathematical proof of correctness (since Stackoverflow is mainly for coding), and I believe from the way I wrote the solution, it should be obvious that the correctness can be derived directly from induction. Nonetheless, I have included the proof for completeness in my latest update as request by the OP.

========================================================================

Solution

You may use a similar approach as in the post you referenced. For simplicity, we only consider finding triangles with right angle at the top-left corner in our discussion. It should be straight forward to generalise our approach to the other cases.

We define a matrix D of the same size as the input matrix, and we initialise all it's entry to 0. We want to use D[i][j] to denote the size of the largest triangle (with right angle at the top-left corner) cornered at (i, j).

Our approach bases on the following observation:

For a triangle of size n at (i, j), it is necessary that we have triangles of size (at least) n - 1 at both (i + 1, j) and (i, j + 1).

We can make use of this fact to compute D using the bottom-up approach. We will compute D iteratively by many passes, where after the n-th pass we will have found all the triangles of size n. We will update D according to the following rules:

1. In the first pass, we set D[i][j] = 1 if the input matrix has 1 at (i, j).

2. In the n-th pass, for each entry in D with value n - 1 (say this entry is at (i, j), we check whether both D[i + 1][j] and D[i][j+1] equal to n - 1, if so, we set D[i][j] = n.

3. We terminate our algorithm when we encounter a pass where no entry of D get updated.

Remark: The n-th pass actually finds all the location of triangles of size n, and we will be using this info to update the next pass, and this is the key idea in dynamic programming - we have found the solution of smaller sub-problems, and we will use it to help solving larger size problems.

The size of the largest triangle (and it's location) can then be found by considering the largest entry of D.

Proof of correctness

This follows trivially by mathematical induction.

Base case: If there is a triangle of size 1 located at (i, j), then we must have D[i,j] = 1 by step (1) of our algorithm.

Inductive step: Suppose we have found all triangles of size n - 1. For any triangle of size n, it follows from the observation that the triangles on it's right (i.e. cornered at (i + 1, j)) and bottom (i.e. cornered at (i, j + 1)) must be of size n - 1. By our induction hypothesis, we have already found these triangles, hence by step (2) of our algorithm we will have D[i, j] = n.

Answer 3

This solution is very smart and elegant. I love it!

However, you can do a slight optimization, because the following assertion is not totaly true:

For a triangle of size n at (i, j), it is necessary that we have triangles of size (at least) n - 1 at both (i + 1, j) and (i, j + 1).

This is not a necessary condition. Here is another (and less restrictive) one:

For a triangle of size n at (i,j) it is egnough that we have a triangle of size (at least) n - 1 in (i-1,j) and a segment of size (at least) n - 1 at the left of (i,j).

This result is less reading in the matrix because it is easy to use an accumulator to find the size of the segment. This results in a reduction of reading of about 33%.

Here is a visual example of the algorithm: http://jsfiddle.net/swvk32e8/1/

function solve() {
    var row, col;
    var i = 0;
    var n;
    var here,above;
    for (row = 1 ; row < SIZE ; row++) {
        n = grid[0 + SIZE * row];
        for (col = 1 ; col < SIZE ; col++) {
            here = grid[col + SIZE * row];
            if (here > 0) {
                if (n > 0) {
                    above = grid[col + SIZE * (row - 1)];
                    grid[col + SIZE * row] = 1 + Math.min(n, above);
                }
                n++;
            } else {
                n = 0;
            }
        }
    }
}