Competitive Algorithms for Maintaining a Mobile Center

摘要

In this paper we investigate the problem of locating a mobile facility at (or near) the center of a set of clients that move independently, continuously, and with bounded velocity. It is shown that the Euclidean 1-center of the clients may move with arbitrarily high velocity relative to the maximum client velocity. This motivates the search for strategies for moving a facility so as to closely approximate the Euclidean 1-center while guaranteeing low (relative) velocity. We present lower bounds and efficient competitive algorithms for the exact and approximate maintenance of the Euclidean 1-center for a set of moving points in the plane. These results serve to accurately quantify the intrinsic velocity approximation quality tradeoff associated with the maintenance of the mobile Euclidean 1-center.