The sensor selection problem for bounded uncertainty sensing models

We address the problem of selecting sensors so as to minimize the error in estimating the position of a target. We consider a generic sensor model where the measurements can be interpreted as polygonal, convex subsets of the plane. This model applies to a large class of sensors including cameras. We present an approximation algorithm which guarantees that the resulting error in estimation is within a factor 2 of the least possible error. In establishing this result, we formally prove that a constant number of sensors suffice for a good estimate-an observation made by many researchers. In the second part of the paper, we study the scenario where the target´s position is given by an uncertainty region and present algorithms for both probabilistic and online versions of this problem.