Optimal Point Movement for Covering Circular Regions
Tóm tắt
Given n points in a circular region C in the plane, we study the problems of moving the n points to the boundary of G to form a regular n-gon such that the maximum (min-max) or the sum (min-sum) of the Euclidean distances traveled by the points is minimized. These problems have applications, e.g., in mobile sensor barrier coverage of wireless sensor networks. The min-max problem further has two versions: the decision version and the optimization version. For the min-max problem, we present an O(nlog2
n) time algorithm for the decision version and an O(nlog3
n) time algorithm for the optimization version. The previously best algorithms for the two problem versions take O(n
3.5) time and O(n
3.5logn) time, respectively. For the min-sum problem we show that a special case with all points initially lying on the boundary of the circular region can be solved in O(n
2) time, improving a previous O(n
4) time solution. For the general min-sum problem, we present a 3-approximation O(n
2) time algorithm. In addition, a by-product of our techniques is an algorithm for dynamically maintaining the maximum matching of a circular convex bipartite graph; our algorithm can handle each vertex insertion or deletion on the graph in O(log2
n) time. This result may be interesting in its own right.
Từ khóa
Tài liệu tham khảo
Akyildiz, I., Su, W., Sankarasubramaniam, Y., Cayirci, E.: Wireless sensor networks: a survey. Comput. Netw. 38(4), 393–422 (2002)
Bhattacharya, B., Burmester, B., Hu, Y., Kranakis, E., Shi, Q., Wiese, A.: Optimal movement of mobile sensors for barrier coverage of a planar region. Theor. Comput. Sci. 410(52), 5515–5528 (2009)
Bremner, D., Chan, T.M., Demaine, E.D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S., Taslakian, P.: Necklaces, convolutions, and X + Y. In: Proc. of the 14th Conference on Annual European Symposium on Algorithms, pp. 160–171 (2006)
Brodal, G., Georgiadis, L., Hansen, K.A., Katriel, I.: Dynamic matchings in convex bipartite graphs. In: Proc. of the 32nd International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 4708, pp. 406–417. Springer, Berlin (2007)
Buss, S., Yianilos, P.: Linear and O(nlogn) time minimum-cost matching algorithms for quasi-convex tours. SIAM J. Comput. 27(1), 170–201 (1998)
Chang, M.S., Tang, C.Y., Lee, R.C.T.: Solving the Euclidean bottleneck matching problem by k-relative neighborhood graphs. Algorithmica 8, 177–194 (1992)
Chen, A., Kumar, S., Lai, T.: Designing localized algorithms for barrier coverage. In: Proc. of the 13th Annual ACM International Conference on Mobile Computing and Networking, pp. 63–73 (2007)
Chen, D.Z., Wang, C., Wang, H.: Representing a functional curve by curves with fewer peaks. Discrete Comput. Geom. 46(2), 334–360 (2011)
Cole, R.: Slowing down sorting networks to obtain faster sorting algorithms. J. ACM 34(1), 200–208 (1987)
Cole, R., Salowe, J., Steiger, W., Szemerédi, E.: An optimal-time algorithm for slope selection. SIAM J. Comput. 18(4), 792–810 (1989)
Dillencourt, M.B., Mount, D.M., Netanyahu, N.S.: A randomized algorithm for slope selection. Int. J. Comput. Geom. Appl. 2, 1–27 (1992)
Efrat, A., Katz, M.J.: Computing Euclidean bottleneck matchings in higher dimensions. Inf. Process. Lett. 75, 169–174 (2000)
Efrat, A., Itai, A., Katz, M.: Geometry helps in bottleneck matching and related problems. Algorithmica 31(1), 1–28 (2001)
Gabow, H., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30, 209–221 (1985)
Hu, S.: ‘Virtual Fence’ along border to be delayed. Washington Post, February 28, 2008
Katz, M., Sharir, M.: Optimal slope selection via expanders. Inf. Process. Lett. 47(3), 115–122 (1993)
Kumar, S., Lai, T., Arora, A.: Barrier coverage with wireless sensors. Wirel. Netw. 13(6), 817–834 (2007)
Liang, Y.D., Blum, N.: Circular convex bipartite graphs: maximum matching and Hamiltonian circuits. Inf. Process. Lett. 56, 215–219 (1995)
Lipski, W. Jr., Preparata, F.P.: Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Inform. 15(4), 329–346 (1981)
Matoušek, J.: Randomized optimal algorithm for slope selection. Inf. Process. Lett. 39, 183–187 (1991)
Megiddo, N.: Applying parallel computation algorithms in the design of serial algorithms. J. ACM 30(4), 852–865 (1983)
Steiner, G., Yeomans, J.: A linear time algorithm for maximum matchings in convex, bipartite graphs. Comput. Math. Appl. 31(2), 91–96 (1996)
Tan, X., Wu, G.: New algorithms for barrier coverage with mobile sensors. In: Proc. of the 4th International Workshop on Frontiers in Algorithmics. Lecture Notes in Computer Science, vol. 6213, pp. 327–338. Springer, Berlin (2010)