Voronoi polygons of general point patterns forced to honeycomb?

Question

This question comes out of a simple wish for graphical displays of people (say members of the Wikimedia chapter for whom I now work) that will display demographic clustering. Obviously in typical developed countries if you place one dot per person you just see blobs for major cities. The usual way is to pull out a map of London (say) on a larger scale. But say that I just want one map.

The following would be a crude thing, but then the idea is just to be able to tell something at a glance. Most countries have various local regions on a fairly small scale. The UK has postcodes, and the initial segment of three to four characters defines regions small enough for most national mapping purposes. The question is motivated by the need to take such postcodes (e.g. NW1) as basic regions. We are going to "round" people to the centroid of their postcode region. Say the ultimate display will be discs at those points of variable colour, or radius.

So now we get the geometry. The centroids of the postcode regions are just some points, and we can define Voronoi polygons for them. (The Earth can be flat: having spherical geometry would be fine, too). What I want is a transformation that forces the Voronoi polygons (large and small) to become tesselating regular hexagons (all of the same area). Such maps seem often to be used, e.g. for electoral maps.

I don't even know the correct language here. We are going to be asking for a non-linear, discontinuous (in general) "map projection", not at all unique and not preserving adjacency. But what I want is something like an existence theorem: is there is a way to do this, that can be computed (once and for all) so that big cities with their small-area polygons are expanded in a fairly sensible way?

If you think about rolling out lumpy dough into a pancake of uniform height, you can perhaps see what I mean. How would it roll out, therefore, under a purely vertical pressing motion? That picture has to be reconciled with the "honeycomb" answer.

Any illumination or references would be very acceptable.

Edit: To clarify: My real question is how to best to show demographic clustering by rescaling of the underlying map, neither creating artefacts, nor hiding genuine clusters. I don't have a good formulation but maybe for smoothed out versions it is like a Radon-Nikodym derivative? But I'm starting with postal data.

Answer 1

If the Voronoi tesselation of a set of points is a honeycomb pattern, then the points are all located at the center of each of the hexagons of the honeycomb, except for the edges. This is only true for a simple Euclidean geometry, of which "London" is a small enough region (steradian/solid angle of the Earth's spherical surface) that a patch of the Euclidean 2-d plane is a reasonable approximation.

So the result you are looking for is going to be a "hexagonal grid", similar to what you would see in board games that have playing fields divided into hexagons. If you limit yourself to small patches of the Earth, say London, or Paris, rather than trying to do it for all of the Earth at once, then a regular hexagonal grid will be fine.

Once you have a regular hexagonal grid, you will have to choose the scale you would like to use (the edge length of the hexagons, or the area encompassed by each of the hexagons). Notice that on the board games, they colour the countries by the hexagon, and approximate the "border" as boundaries between the hexagons, rather than allowing a hexagon to straddle two different countries.

You will always have the problem of deciding between very small hexagons, with many partitions and small populations but better approximations of the boundaries of the post-codes, and larger hexagons, with fewer partitions to deal with each containing larger populations but which will resolve to a poorer approximation of the boundaries of the post-codes. The scale which you decide to use will probably depend upon the nature of the similarity of the members of the group clusters. You may be introducing an artificial group of boundaries which you may not need to.

You may also want to look at k-means clustering as a way of generating a clustering of these data points. It will not give you a regular hexagonal tesselation, but will give you a reasonable approximation of where clusters are located in your data-set. One problem with k-means, fuzzy-c-means, (and similar clustering techniques) is that the centroids are defined by the location of the members of the clusters, and the final segmentation which is reached by the iterative algorithm is strongly dependent upon the choise of the initial points of the clusters, and on the number of clusters ($k$) selected. Selecting the proper number of clusters is essential.

This is usually a big problem for particular data-sets, however, in your case, your desire to use the "city centers" or "post-code centers" as the centers may be an advantage for you in the use of k-means. Set the number of clusters to be the number of post-codes which you wish to use. Set the initial centers of those clusters to be at the "geographic center" of those post-codes. Then let the k-means clustering algorithm run on your data set. The algorithm may coalesce multiple nearby clusters into single clusters.

The end-result of k-means will not be a regular hexagon tesselation. It will, however, give you a good pointer as to which local areas can be categorized together and considered as a single cluster. You can then decrease (or increase) $k$ and rerun the algorithm and allow it to refine the clustering.

---

If you are dead-set on having a regular hexagonal tesselation, perhaps use the k-means to see how far apart the "main" clusters are geographically. Then generate a regular "hexagonal grid" on that scale, and then run a few different simulations where you translate and rotate the regular hexagonal grid to see if there is a particular orientation and scale which best captures the features you wish to ascertain or convey (depending on if you're trying to understand something, or convince someone else of something :) ).

There is no getting around preliminary exploratory data analysis of experimental or phenomenological data sets. Best wishes.