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

[Roger Bivand]

On Thu, 8 Jan 2015, Howard, Tim G (DEC) wrote:

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

Maybe think of this like voter re-districting, and if this applies see:

http://www.jstatsoft.org/v42/i04

and the BARD package (now archived):

http://cran.r-project.org/src/contrib/Archive/BARD/

These apply additional equality criteria to expose Gerrymandering, which 
you may not need. In addition, they often take a fixed number of output 
aggregations, but you are interested in maximising them, so you may need 
to step through these.

Maybe also look at AMOEBA, which is less relevant, I think.

Hope this helps,

Roger

>
> 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]]
>
> _______________________________________________
> R-sig-Geo mailing list
> R-sig-Geo at r-project.org
> https://stat.ethz.ch/mailman/listinfo/r-sig-geo
>

-- 
Roger Bivand
Department of Economics, Norwegian School of Economics,
Helleveien 30, N-5045 Bergen, Norway.
voice: +47 55 95 93 55; fax +47 55 95 91 00
e-mail: Roger.Bivand at nhh.no