טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentScharf Yuval
SubjectCovering Points with a Polygon
DepartmentDepartment of Computer Science
Supervisor Professor Gill Barequet


Abstract

Given a set of points in the plane and a convex polygon, we consider problems in which we try to cover the points (or a maximum number of them) with the given polygon. Depending on the specific problem, we allow the polygon to be translated, rotated, scaled, or any combination of the above.


The problem of covering a set of points using a planar shape is a well-studied area of research in computational geometry. It is important both from a theoretical and a practical point of view.

For example, assume that a measuring device samples the surface of a physical object giving us a set of points describing the object. We also get a description of how the object should look like, and we want to check if the set of points fits the model description. We try to cover the points with the model.

In order to do so we need to translate the model and rotate it.


If the object comes out from a production machine, it is possible that it will not fit the model exactly.

We would like to measure the difference between the physical object (given as a set of sample points) and the model. We want to find the optimum scaling that the model needs to undergo (together with some translation and rotation of it) in order to cover the points.


In this thesis we develop tools that assist in solving the coverage problems. We show how to build them, analyze them, and give examples of how to use them.


We implemented software that demonstrates the results of our research. We describe it and give some screen snapshots of it.