A Caltech Library Service

A Geometric Theorem for Network Design

Franceschetti, Massimo and Cook, Matthew and Bruck, Jehoshua (2004) A Geometric Theorem for Network Design. IEEE Transactions on Computers, 53 (4). pp. 483-489. ISSN 0018-9340.

See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
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.
Subject Keywords:Facility location, combinatorial geometry, network design, wireless networks
Record Number:CaltechAUTHORS:FRAieeetc04
Persistent URL:
Alternative URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5409
Deposited By: Archive Administrator
Deposited On:16 Oct 2006
Last Modified:26 Dec 2012 09:05

Repository Staff Only: item control page