Call
In geometry, a covering of a polygon is a set of primitive units 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 or its vertices.
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.
Talk Doctor Online in Bissoy App