M.Sc Thesis | |

M.Sc Student | Shragai Nadav |
---|---|

Subject | Geometric Covering |

Department | Department of Computer Science |

Supervisor | PROF. Gershon Elber |

Full Thesis text |

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.