An approximation algorithm for the least overlapping p-Frame problem with non-partial coverage for networked robotic cameras

摘要

We report our algorithmic development of the pframe problem that addresses the need of coordinating a set of p networked robotic pan-tilt-zoom cameras for n, (n ≫ p), competing polygonal requests. We assume that the p frames have almost no overlap on the coverage between frames and a request is satisfied only if it is fully covered. We then propose a Resolution Ratio with Non-Partial Coverage (RRNPC) metric to quantify the satisfaction level for a given request with respect to a set of p candidate frames. We propose a latticebased approximation algorithm to search for the solution that maximizes the overall satisfaction. The algorithm builds on an induction-like approach that finds the relationship between the solution to the (p — 1)-frame problem and the solution to the p-frame problem. For a given approximation bound ε, the algorithm runs in O(n/ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> +p <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> /ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">6</sup> ) time. We have implemented the algorithm and experimental results are consistent with our complexity analysis.