CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:FRAieeetc04

[img]
Preview
PDF
See Usage Policy.

831Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:FRAieeetc04

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.


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:http://resolver.caltech.edu/CaltechAUTHORS:FRAieeetc04
Alternative URL:http://dx.doi.org/10.1109/TC.2004.1268406
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5409
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:16 Oct 2006
Last Modified:26 Dec 2012 09:05

Repository Staff Only: item control page