Title:  The ZermeloVoronoi Diagram: a Dynamic Partition Problem 
Author:  Bakolas, Efstathios ; Tsiotras, Panagiotis 
Abstract:  We consider a Voronoilike 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 temporallyvarying drift, which is induced by local winds/currents. As a result, the minimumtime to a destination is not equivalent to the minimumdistance 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 timevarying 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. 
Description:  DOI:10.1016/j.automatica.2010.09.003 
Type:  Preprint 
URI:  http://hdl.handle.net/1853/36874 
ISSN:  00051098 
Citation:  Bakolas, E. and Tsiotras, P., "The ZermeloVoronoi Diagram: a Dynamic Partition Problem,'' Automatica, Vol. 46, No. 12, pp. 20592067, 2010, doi:10.1016/j.automatica.2010.09.003. 
Date:  2010 
Contributor:  Georgia Institute of Technology. School of Aerospace Engineering 
Publisher: 
Georgia Institute of Technology
Elsevier 
Subject: 
Autonomous agents
Voronoi diagram ZermeloVoronoi diagram Dual ZermeloVoronoi diagram Computational methods Dynamic partition problems 
Files  Size  Format  View 

auto10RR.pdf  647.9Kb 
View/
