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

Are there pre-existing algorithms that will determine maximum number of possible polygons (rectangles only, or triangle only) that can "fill" a non regular area in 2D.

share|improve this question

1 Answer 1

I think your question needs sharpening. Perhaps rather than maximum you mean minimum? And what does it mean to "fill" a "non regular area"? Partition? Cover?

If you are interested in partitioning a polygon into triangles, then see the Wikipedia article on "polygon triangulation." If you are interested in covering a polygon with rectangles, then perhaps start with the 1990 paper, "Covering rectilinear polygons by rectangles," IEEE link here. If instead you want to cover with squares, see the earlier MO question, "Covering an arbitrary polygon with minimum number of squares."

share|improve this answer
In addition to the possibilities mentioned above, if you meant packing triangles/squares/rectangles into a polygon, that problem is NP-hard. –  Michael Biro Apr 16 '12 at 2:21
@Michael: Thank you, I should have noted that! –  Joseph O'Rourke Apr 16 '12 at 2:27

Your Answer


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.