This paper studies a deployment problem for a group of robots where individual agents operate with outdated information about each other's locations. Our objective is to understand to what extent outdated information is still useful and at which point it becomes essential to obtain new, up-to-date information. We propose a self-triggered coordination algorithm based on spatial partitioning techniques with uncertain information. We analyze its correctness in synchronous and asynchronous scenarios, and establish the same convergence guarantees that a synchronous algorithm with perfect information at all times would achieve. The technical approach combines computational geometry, set-valued stability analysis, and event-based systems. (C) 2012 Elsevier Ltd. All rights reserved.