M.Sc Student | Goryachev Alex |
---|---|

Subject | Offset-Polygon and Annulus Placement Problems |

Department | Department of Computer Science |

Supervisor | Professor Gill Barequet |

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.