On Aug 26, 2010, at 10:23 AM, Barry Rowlingson wrote:
On Thu, Aug 26, 2010 at 1:50 PM, Sven Schmiedel <s...@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@stat.math.ethz.ch
https://stat.ethz.ch/mailman/listinfo/r-sig-geo
_______________________________________________
R-sig-Geo mailing list
R-sig-Geo@stat.math.ethz.ch
https://stat.ethz.ch/mailman/listinfo/r-sig-geo
