The Zermelo-Voronoi Diagram: a Dynamic Partition Problem

Show full item record

Please use this identifier to cite or link to this item:

Title: The Zermelo-Voronoi Diagram: a Dynamic Partition Problem
Author: Bakolas, Efstathios ; Tsiotras, Panagiotis
Abstract: 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.
Description: DOI:10.1016/j.automatica.2010.09.003
Type: Pre-print
ISSN: 0005-1098
Citation: Bakolas, E. and Tsiotras, P., "The Zermelo-Voronoi Diagram: a Dynamic Partition Problem,'' Automatica, Vol. 46, No. 12, pp. 2059-2067, 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
Subject: Autonomous agents
Voronoi diagram
Zermelo-Voronoi diagram
Dual Zermelo-Voronoi diagram
Computational methods
Dynamic partition problems

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
auto10RR.pdf 647.9Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record