Non-euclidian distance Voronoi diagrams

Question

As a CG novice I was wondering does there exist Voronoi partition that is not based solely on euclidian distance between sites but some other measure, and would such partition still conserve properties of Voronoi diagram?

Reading a textbook I've encountered an example of Voronoi diagram where sites on 2D plane represent football players, and if ball happens to be in Voronoi region of certain player it meant he should go towards it since he's closest to it. Now what if instead of just accounting for the Euclidian distance between players we also considered their speed, with faster players having a larger Voronoi cell.

Would the fact that we lose bisection ruin the structure of Voronoi diagram itself?

Answer 1

Take a look at Power Diagrams and Weighted Voronoï Diagrams. They are generalized Voronoï Diagrams with weights (a circle radius in the case of Power Diagrams) associated with each site.

You can use it to weigh each site with the speed or alter the notion of distance to include speed. By doing so, you will loose the straight line property of bisectors because they might become curved depending on the new distance calculation (look here).

In the case of football players, the new distance function from a point p to a site p_i with player speed v_i is:

d(p, p_i) = EuclideanDistance(p, p_i) / v_i

which can be better interpreted as the time that it takes to reach the point if the player runs at speed v_i. This can produce diagrams like this, where the displayed numbers are the weights 1/v_i: