Polygon covering

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 and on the types of units allowed in the covering. 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 covering can be found in polynomial time.

A unit u contained in a polygon P is called maximal if it is not contained in any other unit in P. When looking for a polygon covering, it is sufficient to consider maximal units, since every unit which is not maximal can be replaced with a maximal unit containing it without affecting the size of the covering.

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

For hole-free polygons, a minimum covering by squares can be found in time O(n), where n is the 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 (- contain uncovered points not covered by other maximal squares) and then deleting from the polygon the points that become unnecessary (- unneeded to support future squares). Here is a simplified pseudo-code of the algorithm:

...
Wikipedia