M.Sc Thesis

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


Covering questions emerge in many disciplines and are closely related to the well known set-cover problem in computer science. Similarly, geometric covering is of great importance and yet has only been investigated in seemingly unrelated specific disciplines. Examples include the well known art-gallery problem, mold-design problems, inspection, security and surveillance problems.

In this thesis, we present a single unified framework that can solve many of the above geometric covering queries. The suggested framework reduces a geometric covering query to the classic computer science set-covering problem, producing a solution of exponential time complexity due to the inherent time complexity of the classic set-covering problem, which is NP-hard. The geometric covering problem (GCP) will be shown to be an NP-hard problem as well. In practice, we are able to efficiently offer almost optimal solutions for small scale geometric covering problems of several covering entities.

Most known algorithms related to geometric covering involve algorithms which often require complex visibility/accessibility analyses of the geometry of the object to be covered in the Euclidean space. The suggested framework reduces the covering analysis to the pixel level and solves the set-covering in the parametric domain of the object, yielding a simple and general framework that, we believe, can be made highly robust. Finally, using the portrayed framework, we demonstrate our implementation with results on mold-design in manufacturing and security.