# A Voronoi diagram with two dimensional generators on a “warped” plane

Consider this set of two dimensional generators (red polygons top left). A Voronoi diagram of these polygons is shown at bottom left. Now consider the same set of two dimensional generators on some "warped" surface (e.g. this banded surface at top right, where each shade of gray represents an amount by which a unit of distance is multiplied; i.e. white=1, black=5). The resulting Voronoi diagram is shown at bottom right.

These were created using a spreading algorithm where points on the boundary of the polygons "spread" at a constant rate. I can make these diagrams, but I would like to know how to explain them using correct terminology.

Can anyone express for me what is going on here in appropriate mathematical terms? (And I would appreciate it if you could correct any incorrect terminology used in posing the question).

I have read this post on Voronoi diagrams with different metric functions, but I don't think this quite what I am after.

-
I am not sure what do you expect. I see nothing wrong with your terminology (i.e. I have understood it without any trouble or doubt), and I have no idea what kind of terminology you would want to use (more fancy or something?), in fact different domains use different names for the same entities. I think the best terminology for you to use is the one that is the most understandable in your area of research (e.g. for you and people you work with)! –  dtldarek Mar 13 '12 at 8:53
Thanks, I appreciate your confidence in my presentation. No not "fancier" necessarily, just a precise alternative means of describing it to a mathematical audience (or in cases where a graphical illustration may not be possible). Actually, the answer given by Rahul Narain was just the sort of insight I was hoping for. –  digitalmaps Mar 13 '12 at 10:39
Great, then let's vote him up ;-) –  dtldarek Mar 13 '12 at 10:53

I believe what you have done here is defined an unusual metric tensor on the square, turning it into a Riemannian manifold. This is automatically a metric space where the distance between any pair of points is the length of the shortest path joining them, as measured by this metric tensor. The notion of the Voronoi diagram, as the collection of the sets of points closest to each generator, generalizes very naturally to any metric space, and that is what you have computed.

(Of course, on a general manifold with a specified metric tensor, you can only compute distances using something like a marching algorithm, which is similar to what you've done by "spreading" the boundaries of the generators.)

-
This really takes it to a new place for me, thanks for introducing several terms with which I had no prior experience. It is interest to discover the pedigree of the spreading algorithm. –  digitalmaps Mar 14 '12 at 1:11