3
$\begingroup$

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.

Can you describe this Voronoi diagram?

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.

  • 0
    Great, then let's vote him up ;-)2012-03-13

1 Answers 1

4

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.)

  • 0
    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.2012-03-14