MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
12

4

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?

flag
3 
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. – Ben Barber Nov 16 at 14:30

1 Answer

8

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.

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

Your Answer

Get an OpenID
or

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