| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Geometric Theorem for Network Design
April 2004 (vol. 53 no. 4)
pp. 483-489
Consider an infinite square grid G. How many discs of given radius r, centered at the vertices of G, are required, in the worst case, to completely cover an arbitrary disc of radius r placed on the plane? We show that this number is an integer in the set \{3,4,5,6\} whose value depends on the ratio of r to the grid spacing. One application of this result is to design facility location algorithms with constant approximation factors. Another application is to determine if a grid network design, where facilities are placed on a regular grid in a way that each potential customer is within a reasonably small radius around the facility, is cost effective in comparison to a nongrid design. This can be relevant to determine a cost effective design for base station placement in a wireless network.
[1] 483 G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, Complexity and Approximation, Appendix B, problem SP8, pp. 426-427. Springer Verlag, 1999.[2] H. Brönninamm and M.T. Goodrich, Almost Optimal Set Covers in Finite VC-Dimension Discrete and Computational Geometry, vol. 14, pp. 463-479, 1995.[3] M. Franceschetti, M. Cook, and J. Bruck, A Geometric Theorem for Approximate Disc Covering Algorithms Electronic Technical report ETR035,http://www.paradise.caltech.eduETR.html, 2001.[4] T. Gonzalez, Covering a Set of Points in Multidimensional Space Information Processing Letters, vol. 40, no. 4, pp. 181-188, 1991.[5] M. Grossglauser and D. Tse, Mobility Increases the Capacity of Ad-Hoc Wireless Networks Proc. Int'l Conf. Information and Comm. (INFOCOM), 2001.[6] P. Gupta and P.R. Kumar, The Capacity of Wireless Networks IEEE Trans. Information Theory, vol. 46, no. 2, pp. 388-404, 2000.[7] D.S. Hochbaum and W. Maass, Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI J. ACM, vol. 32, no. 1, pp. 130-136, 1985.[8] ITU-T Focus Group on Traffic Eng. for Personal Comm., E750-Series of Recommendations on Traffic Eng. Aspects of Networks Supporting Mobile and UPT Services, technical reference Int'l Telecomm. Union, Geneva, 1999.[9] S.R. Kulkarni and P. Viswanath, A Deterministic Approach to Throughput Scaling in Wireless Networks Proc. Int'l Symp. Information Theory (ISIT), p. 351, July 2002.[10] T. Rappaport, Wireless Communications, Principles and Practice. Prentice Hall, 1996.[11] P. Tran-Gia, K. Leibnitz, and K. Tutscku, Teletraffic Issues in Mobile Communication Network Planning Telecomm. Systems, vol. 15, pp. 3-20, 2000.
Index Terms:
Facility location, combinatorial geometry, network design, wireless networks.
Citation:
Massimo Franceschetti, Matthew Cook, Jehoshua Bruck, "A Geometric Theorem for Network Design," IEEE Transactions on Computers, vol. 53, no. 4, pp. 483-489, Apr. 2004, doi:10.1109/TC.2004.1268406
