[R-sig-Geo] best way to find contiguous chunks in a sparse space-time matrix

[Waichler, Scott R]

Hi, I have a space-time sparse grid layout where columns are locations and rows are time.  In general, a location is missing data for some of its times.  I need to subset the layout such that I can represent contiguous blocks of time, wherein for each block of time (rows), all of the selected locations have data.  The tradeoff is that I would like to minimize the number of blocks needed to span the total range in time, while also keeping  as many locations as possible for any given block.  When done, the resulting selection might look like this, where X are non-selected space-time, and the numbers denote selected space-time, 1 . . . k where k is the number of blocks to span the total time range of interest.  

1 1 1 X 1 X 1 1 X  
1 1 1 X 1 X 1 1 X  
1 1 1 X 1 X 1 1 X  
X 2 2 X X 2 2 2 2
X 2 2 X X 2 2 2 2
X 2 2 X X 2 2 2 2
X 2 2 X X 2 2 2 2
X 2 2 X X 2 2 2 2
3 3 X 3 3 3 3 X 3  
3 3 X 3 3 3 3 X 3  
3 3 X 3 3 3 3 X 3  
3 3 X 3 3 3 3 X 3 
. . . 

For starters, I am content to ignore spatial relationships between the locations represented in the columns.  Later, it would be wonderful if I could consider spatial proximity such that a location that has missing values is more likely to be left out of selection if there are nearby locations that have data and can "cover" for the problematic location.  

If anyone has some suggestions on approaches to solve this problem, I would greatly appreciate it.

Thank you,
Scott Waichler
Pacific Northwest National Laboratory
Richland, WA    USA