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
    Commented 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$ Commented 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$ Commented 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
    Commented Nov 18, 2012 at 1:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .