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.
[1] 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: For polygons which may contain holes, finding a minimum such covering is NP-hard.
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 2 opt squares, where opt is the number of squares in a minimum covering:[3] The number of squares in the resulting covering is at most opt + holes, where holes is the number of holes.
This is because an acute angle cannot be covered by a finite number of rectangles.
[13] Finding the smallest set of triangles covering a given polygon is NP-hard.
Note that if we drop the general position assumption, there are polygons in which the triangles in the optimal covering overlap.
The problem of covering only the boundary of a polygon with triangles is NP-complete, but there is an efficient 2-approximation.
[18] The problem is NP-complete when the covering must not introduce new vertices (i.e. Steiner points are not allowed).
-complete, as is the version where a point in the kernel of each star must be contained in an edge of the polygon.
Therefore, a square-covering of the points in S is equivalent to a clique cover of GS.
Finding a smallest square-covering of S is NP-hard; the proof is by reduction from 3SAT.