An Approximation Algorithm for the Least Overlapping $p$-Frame Problem with Non-Partial Coverage for Networked Robotic Cameras Conference Paper uri icon


  • We report our algorithmic development of the p-frame 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 lattice-based 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/3+p2/6) time. We have implemented the algorithm and experimental results are consistent with our complexity analysis. 2008 IEEE.

name of conference

  • 2008 IEEE International Conference on Robotics and Automation

published proceedings

  • 2008 IEEE International Conference on Robotics and Automation

author list (cited authors)

  • Xu, Y., Song, D., Yi, J., & van der Stappen, A. F.

citation count

  • 5

complete list of authors

  • Xu, Yiliang||Song, Dezhen||Yi, Jingang||van der Stappen, A Frank

publication date

  • May 2008