Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Geometric Covering
event speaker icon
Nadav Shragai (M.Sc. Thesis Seminar)
event date icon
Sunday, 18.11.2012, 13:00
event location icon
Taub 337
event speaker icon
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.