3
$\begingroup$

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]

Improve this question
$\endgroup$
2
  • 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$
    – Joseph O'Rourke
    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$
    – Joseph O'Rourke
    Commented Jun 23, 2014 at 12:20

1 Answer 1

Reset to default
3
$\begingroup$

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.

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

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .