Cover a floor with the least amount of planks

Tabeeb

New member
Joined
Oct 19, 2021
Messages
1
The question:
Rectangular planks are sold by the piece, which you are tasked with covering a floor of a room with. These planks come in the same dimensions and can be cut down to any shape, but any pieces that you cut can only have one of the pieces placed on the floor, so if you cut a plank in half or some other shape, you can only lay one-half piece from that plank, and then you will have to throw away the rest and use another plank piece to cover another part of the floor. These planks and plank pieces can be oriented in any way you desire when laying out this floor, given that you are not allowed to place planks outside the boundaries of the floor. Describe a general method to find out the optimal pattern and orientation for these planks in order that the entire area of a given floor is covered, using the least number of planks possible, given that:
- the planks are rectangular,
- planks can be cut to any shape, no matter how complex,
- only one piece of any cut plank must be laid down and the rest discarded,
- the whole internal area bounded by the boundaries of the room must be filled completely by planks,
- the floor shape boundaries are linear, and the floor shape can be at most a complex arrangement of compound shapes, of no more variety than quadrilaterals and triangles, of unlimited permutations of shapes and angles between shapes to your choosing.
- the shape of the floor must be encompassing of a unified area with no breaks/discontinuities such as you can't have two discrete areas which are not adjacent to each other say for example a room can't be two squares merely connected by a single shared vertex,
- the dimensions of the boundaries and angles of the room are variables,
- the dimensions of the length and width of the planks are variables,
You can select the level of complexity of the shape of the floor, that your method is compatible with, where the more floor shapes and of more complexity of the floor shapes that your method accounts for, the higher your method will rank. Remember, the planks are restrained to a simple rectangle of varying dimensions, but when cutting the planks, you can create as complex geometry as you want.

The premise:
I was recently renovating my room with laminate flooring and realised that a perk of laminate flooring is that you can cut it to any shape you want with a hacksaw or a hand tool, and not get necessarily a nice cut with it, but as long as the jagged cuts laid on the border of my walls I could hide them with edge trimmings, but as a result, it made the rest of that cut plank useless as one end would be too ugly and not flush enough to be used in the middle of a room, without messing up the arrangement of the rest of the laminate pieces and it left noticeable gaps of uncovered floor from a slightly concave cut, usually resulting in me having to throw away the rest of the laminate piece after one cut. I thought to myself, surely there must be an effective way to find out mathematically, how best to arrange these laminate pieces in which would cost me the least number of laminate pieces I would have to purchase, given a wide variety of floor shapes, considering the large diversity in floor shape between houses? This deceptively simple question has alluded me for the better part of a month now so I have decided to ask the internet for suggestions, seeing that I have not seen something like this mentioned before in any of my mathematical or other stem-based inquiries, on the internet thus far.
 
Last edited:

mmm4444bot

Super Moderator
Staff member
Joined
Oct 6, 2005
Messages
10,619
 
Top