  We consider the problem of capacitated kinetic clustering in which $n$ mobile
terminals and $k$ base stations with respective operating capacities are given.
The task is to assign the mobile terminals to the base stations such that the
total squared distance from each terminal to its assigned base station is
minimized and the capacity constraints are satisfied. This paper focuses on the
development of \emph{distributed} and computationally efficient algorithms that
adapt to the motion of both terminals and base stations. Suggested by the
optimal transportation theory, we exploit the structural property of the
optimal solution, which can be represented by a power diagram on the base
stations such that the total usage of nodes within each power cell equals the
capacity of the corresponding base station. We show by using the kinetic data
structure framework the first analytical upper bound on the number of changes
in the optimal solution, i.e., its stability. On the algorithm side, using the
power diagram formulation we show that the solution can be represented in size
proportional to the number of base stations and can be solved by an iterative,
local algorithm. In particular, this algorithm can naturally exploit the
continuity of motion and has orders of magnitude faster than existing solutions
using min-cost matching and linear programming, and thus is able to handle
large scale data under mobility.
