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 is a collection of maximal units, possibly overlapping, whose union equals .
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.
Covering a rectilinear polygon with squares
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., unneeded to support future squares). Here is a simplified pseudo-code of the algorithm:
While the polygon P is not empty: Select a continuator square s in P. If the balcony of s is not yet covered, then add s to the covering. Remove the balcony of s from P. If what remains of s is a one-knob continuator, then remove from P a certain rectangle adjacent to the knob, taking care to leave a sufficient security distance for future squares.
For polygons which may contain holes, finding a minimum such covering is NP-hard. This sharp difference between hole-free and general polygons can be intuitively explained based on the following analogy between maximal squares in a rectilinear polygon and nodes in an undirected graph:
Some maximal squares have a continuous intersection with the boundary of the polygon; when they are removed, the remaining polygon remains connected. Such squares are called "continuators" and are analogous to leaf nodes – nodes with a single edge – that can be removed without disconnecting the graph. Other maximal squares are "separators": when they are removed, the polygon splits into two disconnected polygons. They are analogous to nodes with two or more edges that, when removed, leave a disconnected remainder.
In a hole-free rectilinear polygon, all maximal squares are either continuators or separators; thus, such a polygon is analogous to a tree graph. A general polygon is analogous to a general graph. Just like the vertex cover problem is polynomial for tree graphs but NP-hard for general graphs, the square covering problem is linear for hole-free polygons but NP-hard for general polygons.
It is possible to use the linear algorithm to get a 2-approximation; i.e., a covering with at most squares, where opt is the number of squares in a minimum covering: For each hole, find a square s connecting the hole to the external boundary. Cut s from the polygon, then glue back two overlapping copies of s (see figure). The resulting polygon is not planar, but it still 2-dimensional, and now it has no holes. Now use the original algorithm to find a minimum covering.
The number of squares in the resulting covering is at most , where holes is the number of holes. It is possible to prove that . Hence the number of squares in the covering is at most .
Covering a rectilinear polygon with rectangles
For general rectilinear polygons, the problem of finding a minimum rectangle covering is NP-hard, even when the target polygon is hole-free. Several partial solutions have been suggested to this problem: