The Zermelo–Voronoi diagram: A dynamic partition problem

We consider a Voronoi-like partition problem in the plane for a given finite set of generators. Each element in this partition is uniquely associated with a particular generator in the following sense: an agent that resides within a set of the partition at a given time will arrive at the generator associated with this set faster than any other agent that resides anywhere outside this set at the same instant of time. The agent’s motion is affected by the presence of a temporally varying drift, which is induced by local winds/currents. As a result, the minimum time to a destination is not equivalent to the minimum distance traveled. This simple fact has important ramifications over the partitioning problem. It is shown that this problem can be interpreted as a Dynamic Voronoi Diagram problem, where the generators are not fixed, but rather they are moving targets to be reached in minimum time. The problem is solved by first reducing it to a standard Voronoi Diagram by means of a time-varying coordinate transformation. We then extend the approach to solve the dual problem where the generators are the initial locations of a given set of agents distributed over the plane, such that each element in the partition consists of the terminal positions that can be reached by the corresponding agent faster than any other agent.