Optimal Rectangle hatching algorithm

Question

Hi,

I am looking for an algorithm to hatch a rectangle with shortest overall line length, so that an object of given area can be passed through the hatching.

For example given a rectangle of 5x3 cm, and I hatch using parallel lines 1cm across, the biggest object I can pass through the hatch is a square of 1cm side. I have used an overall 22 cm (ie 4x3+2x5) of hatch lines. So to pass an area of 1sqcm I have used 22cm of hatch lines.

The algorithm should find a pattern that minimize the overall hatch lines from current 22cm while not allowing an area with more than 1sqcm to pass through (the object need not be in the form of a square or even rectangle, it's overall area that matters).

Edit: Following the lead of nlucaroni I found the Honeycomb Conjecture which states that any partition of the plane into regions of equal area has perimeter at least that of the regular hexagonal grid, which answers my question partially.

Answer 1

You need shapes that form a tessellation. Hexagon is probably your best bet. Though, what if the shape you are passing through doesn't fit the tessellation pattern exactly?

Look into tessellations and figure out if your pattern/screen/hatch has to be regular or not, has to fit the object being tested, et cetera.

if in fact you are building this from infinite straight lines that form areas = 1, then the best you can do is a square (go ahead, find the maximum of the of area in respect to the ratio of sides, or find perimeter in respect to ratio of sides by taking the derivative).

your question is pretty vague/incomplete, s, this is all i got for you.

Answer 2

What does to hatch a rectangle mean?

Can you rephrase your question?

Also, during the rephrasing, state what the algorithm should receive as input and what it should produce as output.

Answer 3

Neat problem. I suspect that the algorithm is going to end up being really simple, though - there must be some "optimal" set of screen angles to use that minimizes the opening size for a given length of wire.

Actually, this reminds me a bit of the cake-cutting problem, where you're trying to find the minimal number of straight cuts to make x slices of cake. So, the solutiuon may be along the lines of, for each wire, try to make the greatest reduction in the size of the largest object that can pass. That'd mean cutting the largest "holes" in half with each added wire, when possible.

edit: When I actually tried my proposed algorithm, I got results that were worse than the naive version. You definitely need to take the minimum size into account when placing the wires.