A geometric theorem for network design

Massimo Franceschetti

doi:10.1109/TC.2004.1268406

2004-04-01

PRE

Massimo Franceschetti

Matthew Cook

Jehoshua Bruck

DOI：10.1109/TC.2004.1268406

原文链接

原文求助

摘要

En 中文

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.

Keyword:

facility location

combinatorial geometry

network design

wireless networks

期刊

IEEE Transactions on Computers

IF:

3.8

论文数:

5.4K

被引数:

9.8K

机构

暂无机构信息

引用论文

Cholecystokinin Facilitates Glutamate Release by Increasing the Number of Readily Releasable Vesicles and Releasing Probability

The Journal of Neuroscience

IF0

2010-04-14

OAAI

Pan-Yue Deng; Zhaoyang Xiao; Archana Jha; David Ramonet; Toshimitsu Matsui; Michael Leitges; Hee-Sup Shin; James E. Porter; Jonathan D. Geiger; Saobo Lei

Beitr�ge zur Cytologie der Hydra Grisea nebst einigen biologischen Bemerkungen

Zeitschrift f�r Zellforschung und Mikroskopische Anatomie

IF0

1924-01-01

PREAI

J. Gelei

Evaluation of Worker Exposure to Polycyclic Aromatic Hydrocarbons

American Industrial Hygiene Association Journal

IF0

2010-06-04

PREAI

JACQUES LESAGE; GUY PERRAULT; PIERRE DURAND