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?

  • 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 '12 at 14:30

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.

| cite | improve this answer | |
  • $\begingroup$ Since it is Steiner tree like, I imagine you have hit it. Gerhard "Ask Me About System Design" Paseman, 2012.11.16 $\endgroup$ – Gerhard Paseman Nov 16 '12 at 16:16
  • $\begingroup$ @Roland: Very nice improvement! Now the challenge would be to prove this is the (unique?) minimal net... $\endgroup$ – Joseph O'Rourke Nov 17 '12 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 '12 at 1:54

Your Answer

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

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