טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentGoryachev Alex
SubjectOffset-Polygon and Annulus Placement Problems
DepartmentDepartment of Computer Science
Supervisor Professor Gill Barequet


Abstract

The d-annulus of a polygon P is the closed region containing all points in the plane at distance at most d from the boundary of P. An inner (resp. outer) d-offset polygon is a polygon defined by an inner (resp. outer) boundary of its d-annulus.


In this thesis we address three major problems of covering a given point set S by an offset version or a polygonal annulus of a polygon P. First, the Max-Cover objective is, given a value of d, to cover as many points from S as possible by the d-offset (or by the d-annulus) of P, allowing translation and rotation. Second, the Containment problem is to minimize the value of d such that there is a transformation (rotation and translation) of the d-offset (or the d-annulus) of P that covers all points from S. The Partial Containment dilemma is very similar to the Containment problem, only this time we seek the minimum offset of P covering k £ |S| points. We address several variants of these problems, including convex and simple polygons, as well as polygons with holes and sets of polygons.


These problems arise in many applications where one needs to match a given polygonal figure (a known model) to a set of points (usually, obtained measures.)


In order to resolve the above mentioned issues, we exploit two approaches. One approach is based on ”translation-rotation-offset diagrams,” and the other is based on ”stable poses.”


In our first solution we present a two-point translation-rotation-offset diagram, which accumulates the information of all the placements of a given polygon under translation, rotation, and offset that keep two points of S on the boundary of the polygon. We analyze the structure and complexity of this diagram, present an algorithm to build it, and show how it can be used to solve the above problems.


The second solution is based on so-called stable poses. We solve the Containment and Partial Containment problems by enumerating all the ”suspectable” placements of the polygon. The resulting algorithm is rather simple and space-efficient.


We analyze the complexity of our approaches, and also prove that our diagram-based solution is almost optimal among the algorithms that enumerate all the placements of the polygon.