An interesting problem

Matt Lawrence matt.lawrence at virgin.net
Wed Jan 3 15:17:04 GMT 2007

```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
```