Technical Report MSC-2013-27

Title: Geometric Multi-Covering
Authors: Rouven Strauss
Supervisors: Gershon Elber
Abstract: The question of sufficiently covering objects in a geometric space arises in many different disciplines such as inspection, surveillance, lighting design or telecommunication and forms the subject of an abundance of research effort.

In this thesis, we present a general, unified framework to resolve geometric multi-covering problems. The problem is reduced to a linear integer program representing a multi-set multi-cover search in parametric space. We propose and implement different methods for solving the integer program, allowing for flexible trade-offs between solution quality and computation time. Computer graphics techniques are employed as part of the framework's solution in order to compute the input for the integer program.

The highly parallelizable nature of the problem is utilized wherever possible. In contrast to any previous work known to us our approach allows the local specification of coverage requirements. This property is both desirable and necessary in many real-world applications. As part of this thesis, a library offering the functionality for solving geometric covering problems has been implemented. For higher efficiency, the implementation heavily exploits GPU based computations. Our results are demonstrated in two specific applications: firstly, multi-visibility/accessibility analysis of 3D scenes that guarantees visual coverage, possibly redundant, of the target shape(s) by a minimal number of observers. Secondly, illumination design in 3D environments that ensures the satisfaction of local constraints on illuminance levels using a minimal set of lamps.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2013
To the main CS technical reports page

Computer science department, Technion