We consider the problem of characterizing a generalized Voronoi diagram/partition of a convex polygon in a two-dimensional Euclidean space that encodes information about the proximity relations between a team of aerial/marine vehicles and arbitrary points in the partition space. These proximity relations are determined by the time required for each vehicle to reach an arbitrary point (time-to-go) in the partition space when driven by a locally optimal feedback control law in the presence of a spatiotemporal drift field. The main contribution of this work is the presentation of a partitioning algorithm, which is decentralized, in the sense that each vehicle can independently compute its corresponding cell from the generalized Voronoi partition without computing or receiving information about the cells of the other vehicles. Finally, we present numerical simulations using data from real drift fields to illustrate the key features of the decentralized solution to the proposed class of spatial partitioning problems. (C) 2014 Elsevier Ltd. All rights reserved.