Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published April 1, 2004 | public
Journal Article Open

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

FRAieeetc04.pdf
Files (851.5 kB)
Name Size Download all
md5:bc6e52a9a4b4f72621fb5d4e4e9e46ae
851.5 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 16, 2023