Covering With Inexactly Placed Sensors


Authors

Amotz Bar-Noy, T. Brown, M.P. Johnson, O. Liu

Abstract

Abstract—We consider a class of geometric coverage problems in which the objects used to cover the region of interest are, because of practical difficulties, positioned with only approximate accuracy. 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. These include guaranteed and probabilistic coverage of a region using few inexactly placed unit disks, maximizing the sum of the allowable placement errors given a fixed set of disk positions, and choosing error bounds that satisfy max-min fairness, which we do in O(n log n) time. The allowable placement areas need not be disks, however; we conclude with a general method of constructing them. This abstract was presented at the 17th Fall Workshop on Computational Geometry.

Publication Date

November, 2007

Venue

17th Fall Workshop on Computational and Combinatorial Geometry, IBM T.J. Watson Research Center, November 9-10, 2007. http://www.research.ibm.com/people/l/lenchner/fwcg2007/

Published To

Conference


Publication Type

Externally published

ITA Area

Project 8, Technical area 3

Download a copy of the paper here

wiggleroom_0.pdf

Return to main page