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).

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.