17
$\begingroup$

Let $\cal C = \lbrace C_i \rbrace$ be a collection of rectifiable curves in the plane with the property that every unit-length segment meets at least one curve in at least one point. Call such a collection $\cal C$ a needle net: any unit-length "needle" is captured by the net.

I would like to find the sparsest needle net, sparse in the sense that the curves have minimum length per unit area. That is, the limit of $L/A$ of the ratio of the length $L$ of the curves within a region to that region's area $A$, as the region grows large, is as small as possible.

For example, a regular grid of orthogonal parallel lines separated by $\sqrt{2}/2$ is a needle net: the diagonal of each square cell of the grid has length $1$. If I've calculated correctly, the length of its curves (lines) within each unit area region $L/A$ is $2 \sqrt{2}$. See left below, where a unit-length diagonal is highlighted in red, and the region of the plane I used to compute $L/A$ is marked.
   Three Meshes
Again if I've calculated correctly, the equilateral-triangle tiling of the plane obtained from three sets of parallel lines is less efficient, and the packing arrangement of unit-diameter circles shown right above is less efficient still.

Is the square-grid the sparsest needle net? This feels like a question that has been addressed before, perhaps in another guise. If so, a pointer would be welcomed. Thanks!

Update. Roland Bacher's more efficient needle net:
            Hex Tiling
Is this the optimal net?

$\endgroup$
1
  • 3
    $\begingroup$ I've given up trying to work out what it gives you, but you can move the circles in the right hand figure further apart for a small saving. It doesn't look like it will beat the square lattice though. $\endgroup$
    – Ben Barber
    Nov 16, 2012 at 14:30

1 Answer 1

11
$\begingroup$

Without error of my part, a paving with regular hexagons with sides of length $1/2$ gives $L/A=4\sqrt{3}/3\sim 2.3094$. This could very well be the optimal candidate.

$\endgroup$
3
  • $\begingroup$ Since it is Steiner tree like, I imagine you have hit it. Gerhard "Ask Me About System Design" Paseman, 2012.11.16 $\endgroup$ Nov 16, 2012 at 16:16
  • $\begingroup$ @Roland: Very nice improvement! Now the challenge would be to prove this is the (unique?) minimal net... $\endgroup$ Nov 17, 2012 at 1:55
  • 1
    $\begingroup$ It may be not hard in the class of "decent" nets (tilings by convex polygons, say). Just try the argument a la Fejes Toth for planar packings. However, I suspect some monsters may be lurking there... $\endgroup$
    – fedja
    Nov 18, 2012 at 1:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.