2009 | OriginalPaper | Chapter
Cheap or Flexible Sensor Coverage
Authors : Amotz Bar-Noy, Theodore Brown, Matthew P. Johnson, Ou Liu
Published in: Distributed Computing in Sensor Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider dual classes of geometric coverage problems, in which disks, corresponding to coverage regions of sensors, are used to cover a region or set of points in the plane. The first class of problems involve assigning radii to already-positioned sensors (
being cheap
). The second class of problems are motivated by the fact that the sensors may, because of practical difficulties, be positioned with only
approximate
accuracy (
being flexible
). This changes the character of some coverage problems that solve for optimal disk positions or disk sizes, ordinarily assuming the disks can be placed precisely in their chosen positions, and motivates new problems. Given a set of disk sensor locations, we show for most settings how to assign either (near-)optimal radius values or allowable amounts of placement error. Our primary results are 1) in the
1-d
setting we give a faster dynamic programming algorithm for the (linear) sensor radius problem; and 2) we find a
max-min fair
set of radii for the
2-d
continuous problems in polynomial time. We also give results for other settings, including fast approximation algorithms for the
1-d
continuous case.