[R-sig-Geo] group adjacent polygons, optimize sum of polygon attributes

[Howard, Tim G (DEC)]

All,
Given a tessellated set of polygons, each with an attribute of sample size, I want to aggregate these polygons into groups such that the sum of the sample size values reaches a certain threshold while simultaneously maximizing the number of aggregations (groups).   Also, the polygons in the groups (aggregations) would be adjacent.

This seems like a spatial version of the Bin packing problem (http://en.wikipedia.org/wiki/Bin_packing_problem ) or knapsack problem (http://en.wikipedia.org/wiki/Knapsack_problem ).

I can't find reference to relevant optimization approaches to this at the Spatial Task View (http://cran.r-project.org/web/views/Spatial.html ), but I could be looking for the wrong thing.

The closest discussion I've found was this blog entry:

http://www.r-bloggers.com/spatial-clustering-with-equal-sizes/

This is for a relatively small number of polygons that I want to aggregate (perhaps no more than 200), so a brute force method could potentially work, rather than a true optimization?

Otherwise, I'm not sure where to start. Does anyone have any pointers for what to look for?

Thanks in advance,
Tim

	[[alternative HTML version deleted]]