A Geometric Theorem for Network Design
Abstract
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.
Additional Information
© Copyright 2004 IEEE. Reprinted with permission. Manuscript received 16 Dec. 2002; revised 19 Aug. 2003; accepted 10 Nov. 2003. [Posted online: 2004-02-26] This work was partially supported by the Lee Center for Advanced Networking at Caltech.Files
Name | Size | Download all |
---|---|---|
md5:bc6e52a9a4b4f72621fb5d4e4e9e46ae
|
851.5 kB | Preview Download |
Additional details
- Eprint ID
- 5409
- Resolver ID
- CaltechAUTHORS:FRAieeetc04
- Created
-
2006-10-16Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field