Abstract
The minimum disc cover can be used to construct a dominating set on the fly for energy-efficient communications in mobile ad hoc networks, but the approach used to compute the minimum disc cover proposed in previous studies is computationally relatively expensive. In this paper, we show that the disc cover problem is in fact a special case of the general α-hull problem. In spite of being a special case, the disc cover problem is not easier than the general α-hull problem. In addition to applying the existing α-hull algorithm to solve the disc cover problem, we present a simple, yet optimal divide-and-conquer algorithm that constructs the minimum disc cover for arbitrary cases, including those degenerate cases where the α-hull approach would fail.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Basch, J., Erickson, J., Guibas, L.J., Hershberger, J., Zhang, L.: Kinetic collision detection for two simple polygons. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 102–111, 1999
de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry. Springer, Berlin (2000)
Dobkin, D.P., Lipton, R.J.: On the complexity of computations under varying sets of primitives. J. Comput. Syst. Sci. 18, 86–91 (1979)
Edelsbrunner, H., Kirkpatrick, D.G., Seidel, R.: On the shape of a set of points in the plane. IEEE Trans. Inform. Theory IT-29, 551–559 (1983)
Garey, M.L., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Intanagonwiwat, C., Govindan, R., Estrin, D.: Directed diffusion: a scalable and robust communication paradigm for sensor networks. In: Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, pp. 56–67, 2000
Ko, Y.-B., Vaidya, N.H.: Location-aided routing (LAR) in mobile ad hoc networks. In: Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking, pp. 66–75, 1998
Peng, W., Lu, X.: On the reduction of broadcast redundancy in mobile ad hoc networks. In: Proceedings of the First ACM International Symposium on Mobile and Ad Hoc Networking and Computing (MobiHoc), pp. 129–130, 2000
Sun, M., Feng, W., Lai, T.-H., Yamada, K., Okada, H., Fujimura, K.: GPS-based message broadcast for adaptive inter-vehicle communications. In: Proceedings of IEEE International Conference on Parallel Processing, pp. 279–286, 2000
Sun, M., Huang, L., Wang, S., Arora, A., Lai, T.-H.: Reliable MAC Layer Multicast in IEEE 802.11 Wireless Networks, Special Issue of Wiley Wireless Communications and Mobile Computing on Research in Ad Hoc Networking, Smart Sensing, and Pervasive Computing, 2003
Sun, M., Lai, T.-H.: Location aided broadcast in wireless ad hoc network systems. In: Proceedings of IEEE Wireless Communications and Networking Conference, pp. 597–602, 2002
Sun, M., Lai, T.-H.: Computing optimal local cover set for broadcast in ad hoc networks. In: Proceedings of IEEE International Conference on Communications, pp. 3291–3295, 2002
Tseng, Y.-C., Ni, S.-Y., Chen, Y.-S., Sheu, J.-P.: The broadcast storm problem in a mobile ad hoc network. Wirel. Netw. 8(2/3), 153–167 (2002)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sun, MT., Yi, CW., Yang, CK. et al. An Optimal Algorithm for the Minimum Disc Cover Problem. Algorithmica 50, 58–71 (2008). https://doi.org/10.1007/s00453-007-9043-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-007-9043-4