An interesting problem

[Matt Lawrence]

Greg McCarroll wrote:
>
> On 3 Jan 2007, at 14:03, Paul Orrock wrote:
>
>> a project I'm working on and much googling
>
> googling for clustering algorithms might be useful (thanks norman! (we 
> were
> talking about similar problems yesterday)).
>
> G.
>
I would suggest sorting the positive nodes by magnitude, then starting 
with the largest and going down to the smallest, choose the 
highest-value neighbour to make a 2 x 1 rectangle, then sum each square 
or rectangle adjoining the current rectangle and expand it into the 
highest-value neighbour. Repeat until there are no positive adjoining 
rectangles. As you go, remove positive nodes from your original list as 
you include them in the rectangle.

You now have a list of rectangles that can't be expanded by a single row 
or column in any direction without reducing their sums, but there's a 
chance that 2 or more of these will connect up to make an even bigger 
rectangle, i.e. the highest-value rectangle so far is only a *local* 
maximum. Therefore, you would have to sum the intersections of all these 
to be sure that you have the best possible solution.

In the case given, there would only be 3 rectangles, 2 of which are 1 x 
1: XB:CZ, AZ and WA, so you would have to check the sum of WA:CZ so make 
sure it wasn't bigger than XB:CZ.

Matt