# Voronoi polygons of general point patterns forced to honeycomb?

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.

-
The unstated conditions are crucial: otherwise, just take a honeycomb map with the right number of cellsand pick an arbitrary 1-1 correspondence. Quick and easy. A smooth version of the question: given a geographical region and a smooth measure on it, find a map to a rectangle or hexagon or whatever that takes the measure to Lebesgue measure and minimizes the total distortion, perhaps expressed as the $L^1$ norm of the log of the Lipschitz constants for the map and its inverse, or another metric if you prefer. If you don't have a distortion metric in mind, ask explicitly in the question. – Bill Thurston Dec 16 '10 at 0:40
Bill is seeing here more than I am (no surprise!). "[I]s there is a way to do this"? Could you hone your questions into a more concrete form? – Joseph O'Rourke Dec 16 '10 at 1:41
@Joseph: Here's one concrete question: Given a set of points in the plane, can you estimate the minimum number of edge-flip moves to transform the Delaunay triangulation to one where every vertex has 6 edges, and can you construct a transformation within some reasonable bound (say, a factor of 2) of minimality? The boundary makes this a little messy because it can be kept fixed, so it might be worth thinking about the same question for the torus, or a related question on the sphere: one might transform to a triangulation where all vertices have order 5 or 6. – Bill Thurston Dec 16 '10 at 3:41
An answer is given in Baril and Pallo, Efficient lower and upper bounds of the diagonal-flip distance (Inf. Processing Letters, 2006). They actually construct a sequence of moves. A less sharp and easier to understand upper bound is given in "The Edge Flipping Distance of Triangulations," by Hanke et al. Of course, it is not entirely clear that this is what Charles had in mind... – Igor Rivin Dec 16 '10 at 6:25
It'll be quite hard to map, say, hyperbolic geometry to the flat geometry without huge conformal distortions (i.e., if you take the usual disk with hyperbolic lattice (like on Moris Esher's paintings), you are doomed). The situation you should think of first is when you have a big chunk of a small-step lattice surrounded by a big step lattice, so that the whole chunk is just one big hexagon. What do you want to see then? To formalize the task won't be a problem if you can show us a satisfactory mapping in this simplest case. – fedja Dec 16 '10 at 7:00

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.

-
my statements about a regular honeycomb are true if you're asking for each of the hexagons to have the same area, which I believe you are. – sleepless in beantown Dec 16 '10 at 8:31
Thanks for the comments. It seems that experienced cartographers may be able to do a sensible conversion, in a given case, of a map of regions (low valency of the dual graph) into hexagons. But that may be by rule-of-thumb. My real question is how to show demographic clustering by rescaling of the underlying map, neither creating artefacts, nor hiding genuine clusters. Must be "average case" not "worst case" analysis, fairly clearly. – Charles Matthews Dec 16 '10 at 9:23