Efficient algorithms for shared camera control

Abstract

We consider a system that allows n networked users to share control over a robotic webcamera. Each user guides the camera pan, tilt and zoom, by drawing a rectangle in the user interface. The server adjusts the camera to best satisfy the user requests, by solving a geometric optimization problem that requires fitting one rectangle to many. We improve upon previous results with an O(n3/2 log3 n) time exact algorithm for this problem. We also present a simple near-linear time e-approximation algorithm. We have implemented the latter and report on experimental results.