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).