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
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