Discrete mobile Centers

被引：32
作者：
Gao, J [1 ]
Guibas, LJ
Hershberger, J
Zhang, L
Zhu, A
机构：
[1] Stanford Univ, Dept Comp Sci, Stanford, CA 94305 USA
[2] Mentor Graph Corp, Wilsonville, OR 97070 USA
[3] Compaq Syst Res Ctr, Palo Alto, CA 94301 USA
来源：
DISCRETE & COMPUTATIONAL GEOMETRY | 2003年 / 30卷 / 01期
关键词：
D O I：
10.1007/s00454-003-2925-6
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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. This clustering algorithm is distributed in nature and can enable numerous applications in ad hoc wireless networks, where mobile devices must be interconnected to perform various tasks collaboratively.
引用
收藏
页码：45 / 63
页数：19
相关论文
共 26 条
[21]  
Savvides A., 2001, PROC INT C MOBILE CO, P166, DOI DOI 10.1145/381677.381693
[22]  
Sharony J., 1996, Journal of Special Topics in Mobile Networks and Applications (MONET), V1, P75, DOI 10.1007/BF01342734
[23]  
van Lint J., 1992, A Course in Combinatorics
[24]   A new location technique for the active office [J].
Ward, A ;
Jones, A ;
Hopper, A .
IEEE PERSONAL COMMUNICATIONS, 1997, 4 (05) :42-47
[25]  
Wu J, 1999, Proc. ACM Int. Workshop on Discrete Algorithms and Methodsfor Mobile Computing and Communications, P7, DOI DOI 10.1145/313239.33261
[26]  
[No title captured]
123