Discrete Mobile Centers
Abstract:
We propose a new randomized algorithm for maintaining a set
of clusters among moving nodes in the plane. Given a specified
cluster radius, our algorithm selects and maintains a variable subset of the nodes as cluster centers. This subset has the
property that (1) balls of the given radius centered at the chosen nodes cover all the others and (2) the number of centers selected
is a constant-factor approximation of the minimum possible. As the nodes move, an event-based kinetic data structure updates the
clustering as necessary. This kinetic data structure is shown to be responsive, efficient, local, and compact. The produced cover
is also smooth, in the sense that wholesale cluster re-arrangements are avoided. The algorithm can be implemented
without exact knowledge of the node positions, if each node is able to sense its distance to other nodes up to the cluster
radius. Such a kinetic clustering can be used in numerous applications where mobile devices must be interconnected into an
ad-hoc network to collaboratively perform some tasks.
Full paper [ps]
Video Clips:
Random points [25Mb]
Clustered points [15Mb]
