An efficient algorithm for label updating in 2PM model to avoid a moving object.
作者： Farshad Rostamabadi , Mohammad Ghodsi
DOI:
关键词:
摘要: In this paper, we present a simple and fast algorithm for updating labels of set points in presence moving point-shaped object. The are assumed to be axis parallel, unit length, square shaped, each attached exclusively point on one its horizontal (vertical) edges, denoted by 2PM model. updated labeling should include all labels, avoid the with largest possible label length. We allow flip resize operations labeling. known problem, where may their corresponding middle any 4PM model, uses O(n 2 ) preprocessing time O(n) space update O(lg n + k) time, k is number (Rostamabadi Ghodsi, CCCG’04). simpler more efficient that lg n) simplified data structures updates same bound.
tue.nl 参考文章(7)
Joe Marks, Stuart Shieber, The Computational Complexity of Cartographic Label Placement ,(1991)
Zhongping Qin, Alexander Wolff, Yinfeng Xu, Binhai Zhu, New Algorithms for Two-Label Point Labeling european symposium on algorithms. pp. 368- 379 ,(2000) , 10.1007/3-540-45253-2_34
Michael J. Spriggs, J.Mark Keil, A new bound for map labeling with uniform circle pairs Information Processing Letters. ,vol. 81, pp. 47- 53 ,(2002) , 10.1016/S0020-0190(01)00184-3
Rob Duncan, Jianbo Qian, Antoine Vigneron, Binhai Zhu, Polynomial time algorithms for three-label point labeling Theoretical Computer Science. ,vol. 296, pp. 75- 87 ,(2003) , 10.1016/S0304-3975(02)00433-4
TYCHO STRIJK, ALEXANDER WOLFF, Labeling points with circles International Journal of Computational Geometry and Applications. ,vol. 11, pp. 181- 195 ,(2001) , 10.1142/S0218195901000444
Farshad Rostamabadi, Mohammad Ghodsi, A Fast Algorithm for Updating a Labeling to Avoid a Moving Point canadian conference on computational geometry. pp. 204- 208 ,(2004)
ALEXANDER WOLFF, MICHAEL THON, YINFENG XU, A SIMPLE FACTOR-2/3 APPROXIMATION ALGORITHM FOR TWO-CIRCLE POINT LABELING International Journal of Computational Geometry and Applications. ,vol. 12, pp. 269- 282 ,(2002) , 10.1142/S0218195902000888