Polygon covering

In geometry, a covering of a polygon is a set of primitive units (e.g. squares) whose union equals the polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covered. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon. In some scenarios, it is not required to cover the entire polygon but only its edges (this is called polygon edge covering) or its vertices (this is called polygon vertex covering). In a covering problem, the units in the covering are allowed to overlap, as long as their union is exactly equal to the target polygon. This is in contrast to a packing problem, in which the units must be disjoint and their union may be smaller than the target polygon, and to a polygon partition problem, in which the units must be disjoint and their union must be equal to the target polygon. A polygon covering problem is a special case of the set cover problem. In general, the problem of finding a smallest set covering is NP-complete, but for special classes of polygons, a smallest polygon time. A covering of a polygon P is a collection of maximal units, possibly overlapping, whose union equals P. A minimal covering is a covering that does not contain any other covering (i.e. it is a local minimum). A minimum covering is a covering with a smallest number of units (i.e. a global minimum). Every minimum covering is minimal, but not vice versa. A rectilinear polygon can always be covered with a finite number of vertices of the polygon. The algorithm uses a local optimization approach: it builds the covering by iteratively selecting maximal squares that are essential to the cover (i.e., contain uncovered points not covered by other maximal squares) and then deleting from the polygon the points that become unnecessary (i.e.