Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm very lost, and just trying to figure out where to start to get the answer to the below problem: How do you solve for the orientation of spacing objects (few objects as possible while having the entire room area covered by the objects) within a room? I'm sure it's some kind of algorithm but I don't even know where to get started. For example if you needed to space 10 by 10 geometrical squares in a room that is 10 by 10, you can fit one 10 by 10 square in the room. If you have a room that is 100 by 100 (area=10,000), you can fit 100 squares in the room, with no 'empty' space left over, which is the key.

It gets messy when you need to figure out the minimal number of squares you can fit in a room while covering the entire area of the room with the squares, when the room is a triangle. Obviously squares don't fit that well into triangles, so now we can introduce the next rule: squares can overlap eachother, and be cut off by the outer edges of the room. So now you can stick a square in the corner of the triangle. Problem solved easily enough. But how do you figure out the optimal spacing orientation of the squares in the room in order to use the minimal amount of squares?

I would also LOVE to know if similar algorithms already exist and what they are called. I found some algorithms called 'bin packing' algorithms but these are different - they are trying to fit the maximum possible stuff inside a room - doesn't account for overlapping geometric squares - also if you only have an objects of a fixed size shouldnt there be no need for heuristics or other 'guesswork'? But an actual concrete formula?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

You are describing "covering problems" rather than "packing problems". In general, there are no exact formulas for either kind of problem, only asymptotics, and exact answers for small numbers. The Geometry Junkyard has a lot of links to get you started. Another good site is Erich's Packing Center. For example, you'll find covering triangles with squares there.

share|improve this answer

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.