Return to Answer

To address Helena's comment about keeping only two dominating cells, here's an example matrix which I think shows this doesn't work in general:

The above shows the state of the filter after the first two dominating cells are found. We can see there are 3 areas still free, including a 4X4 middle area. By induction if we can create empty sub-matrices, then these can be further subdivided as well in the same manner which can be seen once the 7 cell is handled. There's some upper limit to the number to this for any given N that, if generalized, might be potentially useful for optimization.

The filter complexity is based on the fact that you cannot have more than n results in the output (which I'm fairly certain is true.) If I'm not mistaken about that, you can exit the filter loop once the results are of length N. You might also be able to get fancy around keeping track of non-dominated cells. Once there are no more unoccupied, non-dominated cells in the results, you are done. These don't necessarily change the O-time but can have impact on the actual performance of a real program.

The filter complexity is based on the fact that you cannot have more than N results in the output (which I'm fairly certain is true.) If I'm not mistaken about that, you can exit the filter loop once the results are of length N. You might also be able to get fancy around keeping track of non-dominated cells. Once there are no more unoccupied, non-dominated cells in the results, you are done. These don't necessarily change the O-time but can have impact on the actual performance of a real program.