After reading many papers about problems of minimum polygon covering, I found out that there are four different types of units that are considered for covering polygons, in increasing order of generality: squares, rectangles, convex shapes and star shapes.

In theory, there can be many other covering units, for example: it is possible to cover a polygon with triangles (this is different than the problem of triangulation because the units in a covering may overlap), pentagons, hexagons... but, I haven't found any paper discussing such covering problems.

My question is: are you aware of any papers discussing the problem of finding a minimum covering of a polygon with shapes other than the four classes above?

I am particularly interested in covering a polygon with right-angled isosceles triangles, isolateral triangles or other regular polygons.

[NOTE: Cross-posted from cs.SE after I received the Tumbleweed badge for it]

  • 2
    $\begingroup$ Also covering by spirals were considered in this paper: O'Rourke, J.; Supowit, K. (1983). "Some NP-hard polygon decomposition problems". IEEE Transactions on Information Theory 29 (2): 181. $\endgroup$ Commented Jun 23, 2014 at 12:19
  • 1
    $\begingroup$ Also partitions into L-shapes have been studied, but I do not recall work on covers by L-shapes... $\endgroup$ Commented Jun 23, 2014 at 12:20

1 Answer 1


There is a recent paper by Tobias Christ that extends the covering work I cited in the comments, and work by Andrejz Lingas, to triangles, one of the problems left unresolved by that earlier work. Tobias shows, via an intricate construction, that the minimum cover of a simple polygon by triangles is also NP-hard:

Christ, Tobias. "Beyond triangulation: covering polygons with triangles." Algorithms and Data Structures. Springer Berlin Heidelberg, 2011. 231-242. (Springer link)

The paper also contains a nice, up-to-date summary of work in this area.

      Christ Fig.1: Gadgets in the NP-hardness construction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.