The Taub Faculty of Computer Science Events and Talks
Nadav Shragai (M.Sc. Thesis Seminar)
Sunday, 18.11.2012, 13:00
Advisor: 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.