Patent ID: 7113955

Claim:
A method for determining maximal homogeneous target-value rectangles for a binary matrix, the method comprising the steps of: sequentially selecting each entry (x, y) from row y and column x in the matrix, the sequence for selection being ordered first by lowest row to highest row, and within each row from lowest column to highest column, for each selected entry (x, y), determining the entries in a staircase (x, y) data structure, the staircase (x, y) data structure comprising entries corresponding to entries in the matrix, each entry in the staircase (x, y) data structure corresponding to a step in a staircase-shaped region of the matrix having target-value entries only, the staircase-shaped region having a first boundary defined by column x and having a second boundary defined by row y, extracting maximal rectangles for entry (x, y) by removing from the staircase (x, y) data structure, and storing as part of a set of maximal homogeneous rectangles for the matrix, each entry in the staircase (x, y) data structure corresponding to a maximal rectangle of target-values, where the said rectangle is characterized by a corner with the highest x column value and highest y row value being entry (x, y).