Pan and scan: Configuring cameras for coverage

We introduce the pan and scan problem, in which cameras are configured to observe multiple target locations. This is representative example within a broad family of problems in which multiple sensing devices are deployed, each in general observing multiple targets. A camera´s configuration here consists of its orientation and its zoom factor or field of view (its position is given); the quality of a target´s reading by a camera depends (inversely) on both the distance and field of view. After briefly discussing an easy setting in which a target accumulates measurement quality from all cameras observing it, we move on to a more challenging setting in which for each target only the best measurement of it is counted. Although both variants admit continuous solutions, we observe that we may restrict our attention to solutions based on pinned cones. For a geometrically constrained setting, we give an optimal dynamic programming algorithm. For the unconstrained setting of this problem, we prove NP-hardness, present efficient centralized and distributed 2-approximation algorithms, and observe that a PTAS exists under certain assumptions. For a synchronized distributed setting, we give a 2-approximation protocol and a (2β)/(1 - α)-approximation protocol (for all 0 ≤ α ≤ 1 and β >; 1, though satisfying these constraints with equality will in different ways trivialize the guarantees) with the stability feature that no target´s camera assignment changes more than log_β(m/α) times. We also discuss the running times of the algorithms and study the speed-ups that are possible in certain situations.