[R-sig-Geo] splitting a map into areas by number of addresses

[Nikhil Kaza]

On Aug 26, 2010, at 10:23 AM, Barry Rowlingson wrote:

> On Thu, Aug 26, 2010 at 1:50 PM, Sven Schmiedel <sven at cancer.dk>  
> wrote:
>> Dear list,
>>
>> I have the following problem: I have around 1,000,000 addresses of  
>> a country and want now to split the area in artificial  
>> "administrative units" with exactly 1,000 addresses per unit.
>>
>> As I did not find a direct way to do this, my idea was to chose  
>> randomly 1,000 addresses, use the voronoi tessellation (from  
>> library PBSmapping) for these and look how many addresses are found  
>> in each piece this mosaic. However, the result is not stable and  
>> the number of addresses varies quite a lot from unit to unit.
>>
>> Hence, I would like to know if there is a procedure/package that is  
>> incorporating a function that is able to do this splitting with a  
>> fixed number of addresses. If anyone has another program or an  
>> methodological approach to this problem I would be happy about this  
>> information.
>
> Hmmm as stated this doesn't look particularly well-defined.
>
> Do the administrative units have to be compact and connected? If not,
> then just do sample(1000,1000000,TRUE) and job done.
>
> Do you have point locations for each address, or areas? You didn't  
> say.
>
> With point locations you could do the voronoi tesselation of all
> 1000000 and then take the graph and partition it into 1000 connected
> sub-graphs [waves hands] somehow. That would ensure all addresses in
> an admin unit were neighbours, but you could have an admin unit that
> was a linear feature of addresses.
>
> I can think of various heuristics for making more compact sets, which
> involve growing units by adding the next nearest address that
> minimizes the 'spread', possibly by adding the next unit as the one
> nearest the centroid of the current unit. You might want to grow all
> 1000 simultaneously from 1000 seeds (spread across the area) or grow
> one to full size, and then another, but that might form lots of
> 'islands' of less than 1000 addresses that would be impossible to form
> into admin units.
>
> Barry
>

Graph partitioning is NP-complete. However, heuristics exist that work  
in a resonable time for real world graphs. see http://en.wikipedia.org/wiki/Kernighan%E2%80%93Lin_algorithm 
. But I doubt if this would work for your situation.
Another idea, is to create 1000 clusters (not sure how you would  
ensure exactly 1000 points in each).  Find the centeroid of those  
clusters and then create the Voronoi tessellation.

> _______________________________________________
> R-sig-Geo mailing list
> R-sig-Geo at stat.math.ethz.ch
> https://stat.ethz.ch/mailman/listinfo/r-sig-geo