Technical Report MSC-2013-09

Title: Geometric Covering
Authors: Nadav Shragai
Supervisors: Gershon Elber
Abstract: 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 speci c disciplines. Examples include the well known art-gallery problem, mold-design problems, inspection, security and surveillance problems. In this thesis, we present a single uni ed 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 eciently o er 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.

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