5
$\begingroup$

Imagine you want to make a net out of string to filter and catch objects of a certain size, minimizing the length of string employed. (This actually arises in filtering biological impurities from water.) One way to model the problem is as follows.

A net $N$ is a connected, infinite plane graph with no vertex of degree $1$. The objects to be caught are all convex shapes $C$ of area $\ge 1$:


      Area1Convex
Above, the disk has radius $r=1/\sqrt{\pi} \approx 0.56$, the square is $1 \times 1$, etc.

A shape $C$ can pass through the net if there is some positioning of $C$ such that the closed shape $C$ shares no point with $N$. Otherwise $C$ is caught by the net $N$. Let $\cal C$ be the set all convex shapes $C$ of area $\ge 1$.

A natural net is an orthogonal grid, a tiling of the plane by $1 \times 1$ squares. It seems clear this catches all shapes in $\cal C$. Its efficiency can be measured by the length of string per unit area of the plane. For this grid, this $L/A$ ratio is $2$.

But a tiling of the plane by unit-area hexagons is more efficient. The edge length of such a hexagon is $\frac{\sqrt{2}}{3^{3/4}} \approx 0.62$; its incircle radius is $\frac{1}{\sqrt{2} \sqrt[4]{3}} \approx 0.54$. Here it is shown superimposed on the unit-area disk, which it clearly catches.


      HexDisk
This hexagonal tiling seems to catch all shapes in $\cal C$, and if I've calculated correctly, its $L/A$ ratio is $\frac{3^{3/4}}{\sqrt{2}} \approx 1.61$.

Q. Is there a more efficient net than this hexagonal tiling?

I asked an analogous question two years ago, "The sparsest planar net that captures every unit segment," whose answer might also be a hexagonal tiling. The current question is more like an isoperimetric problem, and might have been explored already in that context. If anyone knows, I'd appreciate a pointer. Thanks!


Answered by Yoav Kallus. My problem is "equivalent to asking what is the least mean length partition of the plane into cells of area at most $1$." It is therefore "equivalent to the Honeycomb problem, which was solved by [Thomas] Hales" in 1999, just 2035 years since it was "conjectured" by Varro :-). So the hexagonal tiling described above is indeed optimal, but certainly not obviously so. The answer to Q is therefore: No.

$\endgroup$
  • $\begingroup$ @JosephORourke do your nets have to be polygonal meshes? Would be interesting, if a dense packing of circles is better. $\endgroup$ – Manfred Weis Oct 31 '14 at 12:28
  • $\begingroup$ @ManfredWeis: That would be interesting, if a specialization (e.g., to polygonal nets) would be less efficient. $\endgroup$ – Joseph O'Rourke Oct 31 '14 at 12:32
  • 3
    $\begingroup$ Without the restriction to convex objects, this is equivalent to asking what is the least mean length partition of the plane into cells of area at most 1. Clearly if all cells are of area no more than 1, a shape of area one cannot be contained in a cell (which is the only way to filter through the net). Also, if any cell is of area more than 1, then a slightly contracted version of it is a shape that passes through the net. $\endgroup$ – Yoav Kallus Oct 31 '14 at 12:47
  • 3
    $\begingroup$ I suspect that this is indeed equivalent to the Honeycomb problem, which was solved by Hales. $\endgroup$ – Yoav Kallus Oct 31 '14 at 12:49
  • $\begingroup$ I should say, my relaxation to nonconvex objects still assumes connectedness of the objects (which is natural, as otherwise no net works). $\endgroup$ – Yoav Kallus Oct 31 '14 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.