Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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]

share|improve this question
2  
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. –  Joseph O'Rourke Jun 23 at 12:19
1  
Also partitions into L-shapes have been studied, but I do not recall work on covers by L-shapes... –  Joseph O'Rourke Jun 23 at 12:20

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
1  
Thanks a lot. I updated the Wikipedia page. –  Erel Segal Halevi Jun 26 at 12:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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