Decomposition-Based Optimization of Multi-camera Networks for Coverage Maximization Problem

The proliferation of low-cost, high-efficiency surveillance cameras has made multi-camera networks a ubiquitous tool for security and monitoring in public spaces. However, the optimal placement of these cameras to maximize coverage while minimizing resources presents a significant and computationally complex challenge, known to be NP-hard. This research introduces a novel and effective model to address the camera planning problem. We formulate the problem and propose a decomposition strategy that partitions the main problem into smaller, manageable subproblems based on a neighbor graph of potential camera locations. This decomposition allows for the efficient application of well-established solvers to find optimal or near-optimal solutions within practical time constraints. Our model utilizes a 2D map visualization of sensor views, which simplifies the calculation of coverage areas and ensures the direct applicability of our solutions to real-world scenarios. Experimental results, conducted on a set of candidate locations within a university campus, demonstrate the proposed model’s superior performance. The formulation successfully maximizes spatial coverage under limited computational budgets, validating its effectiveness and potential for deployment in practical surveillance network design. This approach offers a significant advancement in strategic camera placement, providing a scalable and efficient solution to a critical security problem.