M.Sc Thesis

M.Sc StudentStrauss Rouven
SubjectGeometric Multi-Covering
DepartmentDepartment of Computer Science
Supervisor PROF. Gershon Elber
Full Thesis textFull thesis text - English Version


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.