VC-Dimension of Exterior Visibility of Polyhedra

In this paper, we address the problem of finding the minimal number of viewpoints outside a polyhedron in two or three dimensions such that every point on the exterior of the polyhedron is visible from at least one of the chosen viewpoints. This problem which we call the minimum fortress guard problem (MFGP) is the optimization version of a variant of the art-gallery problem (sometimes called the fortress problem with point guards) and has practical importance in surveillance and image-based rendering. Solutions in the vision and graphics literature are based on image quality constraints and are not concerned with the number of viewpoints needed. The corresponding question for art galleries (minimum number of viewpoints in the interior of a polygon to see the interior of the polygon) which we call the minimum art-gallery guard problem (MAGP) has been shown to be NP-complete. A simple reduction from this problem shows the NP-completeness of MFGP. Instead of relying on heuristic searches, we address the approximability of the camera placement problem. It is well known (and easy to see) that this problem can be cast as a hitting set problem. While the approximability of generic instances of the hitting set problem is well understood, Brönnimann and Goodrich[3] presented improved approximation algorithms for the problem in the case that the input instances have bounded Vapnik-Chervonenkis (VC) dimension. In this paper we explore the VC-dimension of set systems associated with the camera placement problem described above. We show a constant bound for the VC dimension in the two dimensional case but a tight logarithmic bound in the three dimensional case. In the two dimensional case we are also able to present an algorithm that uses at most one more viewpoint than the optimal in the case that the viewpoints are restricted to be on a circumscribing circle - a restriction that is justified in practice.