splitting a map into areas by number of addresses

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