Geometric Covering

Nadav Shragai, M.Sc. Thesis Seminar
Sunday, 18.11.2012, 13:00
Taub 337
Prof. Gershon Elber

Covering questions emerges 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. The solution is of exponential complexity due to the inherent complexity of the classic set-covering problem. However, in practice, we are able to efficiently offer almost optimal solutions for small scale problems of several covering entities. Finally, using the portrayed framework, we demonstrate results on mold-design in manufacturing and security.

Back to the index of events