Valentin Polishchuk · Jukka Suomela

Optimal backlog in the plane

Algosensors 2008 · 4th International Workshop on Algorithmic Aspects of Wireless Sensor Networks, Reykjavík, Iceland, July 2008 · doi:10.1007/978-3-540-92862-1_12

authors’ version publisher’s version


Suppose that a cup is installed at every point of a planar set P, and that somebody pours water into the cups. The total rate at which the water flows into the cups is 1. A player moves in the plane with unit speed, emptying the cups. At any time, the player sees how much water there is in every cup. The player has no information on how the water will be poured into the cups in the future; in particular, the pouring may depend on the player's motion. The backlog of the player is the maximum amount of water in any cup at any time, and the player's objective is to minimise the backlog. Let D be the diameter of P. If the water is poured at the rate of 1/2 into the cups at the ends of a diameter, the backlog is Ω(D). We show that there is a strategy for the player that guarantees the backlog of O(D), matching the lower bound up to a multiplicative constant. Note that our guarantee is independent of the number of the cups.


Sándor P. Fekete (Ed.): Algorithmic Aspects of Wireless Sensor Networks, Fourth International Workshop, ALGOSENSORS 2008, Reykjavik, Iceland, July 2008, Revised Selected Papers, volume 5389 of Lecture Notes in Computer Science, pages 141–150, Springer, Berlin, 2008

ISBN 978-3-540-92861-4

Journal Version

© Springer 2008

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.