Illuminate the Sphere

Jim Mahoney, March 2010

The problem

From Technology Review's Puzzle Corner (http://cs.nyu.edu/~gottlieb/tr/back-issues/),  May 2005 :

Place the minimum number of lamp posts needed to illuminate the entire (spherical) planet.  Oh yes, you are also to arrange that the total length of all the posts is minimal (among solutions with the minimal number of posts).

We've also been talking about a harder problem, more analogous to the "illuminate the equator", namely making the sum of all the lamp post heights as small as possible.

Discussion

You can't do it with three posts.  The lamps then form a plane, which cuts the sphere into two regions, and at least one of the centers of those regions will be dark.

You can do it with four posts, set at the vertices of a tetrahedron. 

Let the height of a post be x, and let the radius of the sphere be 1.  The furthest spot that's illuminated is the top point (the north pole) in the diagram below, where a line from the top of the pole is tangent to the sphere, and making an angle α with the pole.  The radius of the circle of illlumination is the line in green, which has length sin(α) as shown.

diagram code

diagram=Graphics[{
Circle[{0,0},1,{π/4,3π/4}],
Blue,
Line[{{0,0},{0,1}}],
Line[{{0,0},r}],
Line[{r,{0,1}}],
Green,
Line[{{0,1},Cos[α] rHat}],
Gray,
Circle[{0,0},.15,{π/2-α,π/2}],
Text["α",{.05,.2}],
Text["1",.5 r+{.2,0}],
Text["x",.85r+{.2,0}],
Text["sin(α)",(Cos[α]rHat+{0,1})/2+{0,-.2}],
Arrowheads[{-.02,.02}],
Arrow[{.05{1,-1},rHat+.05{1,-1}}],
Arrow[{rHat+.05{1,-1},r+.05{1,-1}}],
Arrow[{{0,1}+.05{-1,-1},Cos[α]rHat+.05{-1,-1}}]
}];

diagram

x=1/Cos[α]-1;
rHat = {Sin[α],Cos[α]};
r = (1+x)rHat;
diagram/.α->π/5

Putting three lamp posts at equal angles around the north pole of the sphere and a fourth at the south pole gives the following diagram.

definitions

origin={0,0,0}; 
i={1,0,0};
j={0,1,0};
k={0,0,1};
spherical[r_,θ_,ϕ_]:=r{Sin[θ]Cos[ϕ],Sin[θ]Sin[ϕ],Cos[θ]};

r1=spherical[1+x,α,0];
r2=spherical[1+x,α,2π/3];  
r3=spherical[1+x,α,4π/3];
r4= spherical[1+x,π,0];
r1Hat=r1/Norm[r1];
r2Hat=r2/Norm[r2];
r3Hat=r3/Norm[r3];
r4Hat=r4/Norm[r4];

3D picture code

circle3D[center_, axis_,radius_]:=Cylinder[{
center+axis*0.0001,(* A circle is a nearly zero height cylinder. *)
center-axis*0.0001
},radius];
picture=Graphics3D[{
Gray,Thin,
Line[{origin,r1Hat}],Line[{origin,r2Hat}],
Line[{origin,r3Hat}],Line[{origin,r4Hat}],
Blue,AbsoluteThickness[3],
Line[{r1Hat,r1}],Line[{r2Hat,r2}],
Line[{r3Hat,r3}],Line[{r4Hat,r4}],
LightBlue,Thin,
Line[{r1,k}],Line[{r2,k}],Line[{r3,k}],
Line[{r1,r2}],Line[{r2,r3}],Line[{r3,r1}],
(*  Transparent,EdgeForm[Green],circle3D[origin,k,1], *)
EdgeForm[Yellow],Cyan,Opacity[0.2],
Cone[{Cos[α]r1Hat,r1},Sin[α]],
Cone[{Cos[α]r2Hat,r2},Sin[α]],
Cone[{Cos[α]r3Hat,r3},Sin[α]],
Cone[{Cos[α]r4Hat,r4},Sin[α]],
White,Opacity[0.3],
Sphere[origin,1]
}, Boxed->False];

tetrahedron

For a tetrehedron, all the angles between the lamp posts must be the same, which lets us solve for α.  As you can see in the picture, the cones of light just barely cover the whole area.

Solve[r1Hat . r2Hat == r1Hat . r4Hat, α]

picture/.α->ArcSec[3]

The total length of the poles is

4 x /.α->ArcSec[3]

And by the definition of secant and arcsecant,

Cos[ArcSec[3]]

more posts

As the number of lamp posts increase, those four posts look something like this.

picture /. α->Pi/16

Clearly the best arrangement will still have the illumination from three lamps meeting at one point, as above.  But how those circles of illumination pack together on the surface of a sphere depends on how big the circles are.  Or at least, it does when the circles are big compared to the size of the sphere.

In the limit as the number of posts gets big and the heights of the post get small, the surface of the sphere will be a good approximation to a plane, and in that case the situation is pretty simple: we just overlap the circles of light like this :

circles diagram code

h={Cos[π/3],Sin[π/3]};
circles=Graphics[
{Gray,
Table[Circle[i h + j{1,0},1/Cos[π/6]],{i,1,5,2},{j,1,5,2}]}
];

circles diagram

circles

Essentially each lamp post is responsible for the hexagon underneath it.

We know that the radius of each of these circles is sin(α), and so that's also the side of each hexagon.

hex diagram code

r1={Sin[π/3],Cos[π/3]};
r2={Sin[2π/3],Cos[2π/3]};
hex=Graphics[{
Gray,
Text["sin(α)",{1.2,0}],
Text["red area = \!\(\*Cell[TextData[Cell[BoxData[
FormBox[
RowBox[{
FractionBox[
SqrtBox["3"], "2"], 
RowBox[{
SuperscriptBox["sin", "2"], "(", "α", ")"}]}], TraditionalForm]],
FormatType->"TraditionalForm"]]]\)",{0,.5}],
Arrowheads[{-.02,.02}],
Arrow[{r1+{.1,0},r2+{.1,0}}],
Transparent,EdgeForm[Black],
Polygon[Table[{Sin[x],Cos[x]},{x,0,2π,π/3}]],
Red,Opacity[.3],
Polygon[{{0,0},r1,r2}]
}];

hex diagram

hex

A bit of simple geometry tells us that the area of the hexagon is made of six triangles, each with area ((Sqrt[3])/8)((sin^2)α), so the hexagon area is (3/4)(Sqrt[3])(sin^2)α.

Since we know that the area of the sphere is 4π (since the radius is 1), that gives us an estimate of how many lamp posts N are needed in this large N limit.  While this is only an approximate result, I expect that the fractional error gets small as N gets big and α gets small.

So we have

4π ~ N 3(Sqrt[3])(sin^2)α		in the large N, small α limit	
or
	N = ((4π)/(3 (Sqrt[3])(sin^2)α))

In this limit, that gives

total post length = N x = ( ((16π)/(3 (Sqrt[3])(sin^2)α)))(1/cos(α)-1)		as α goes to zero.

totalPostLength[α_]:=( ((16π)/(3 (Sqrt[3])((Sin[α])^2))))(1/Cos[α]-1)

Plot[totalPostLength[1/z],{z,1,40},PlotRange->{Automatic,{4.0, 8.0}}]

D[totalPostLength[1/z],z]

Plot[((32 π Cot[(1/z)] ((Csc[(1/z)])^2) (-1+Sec[(1/z)]))/(3 (Sqrt[3]) (z^2)))-((16 π Csc[(1/z)] ((Sec[(1/z)])^2))/(3 (Sqrt[3]) (z^2))),{z,1,40}]

Interesting.  This heads towards a constant value, which we can see by looking at the taylor expansion of the numerator and denominator.

total post length = (((16π)/(3(Sqrt[3])))) ((1 - cos(α))/(cos(α) (sin^2)(α)))
		= (((16π)/(3(Sqrt[3])))) ((1 -(1 - ((α^2)/2)+O((α^4))))/((1 - ((α^2)/2)+O((α^4)))(((α-((α^3)/(3!))+O((α^5))))^2)))
			= (((16π)/(3(Sqrt[3])))) ((((α^2)/2)+O((α^4)))/((1 - ((α^2)/2)+O((α^4)))((α^2)+O((α^4)))))
			= (((16π)/(3(Sqrt[3])))) ((((α^2)/2)+O((α^4)))/((α^2)+O((α^4))))     = (((16π)/(3(Sqrt[3])))) ((1/2))

totalPostHeight=8π/(3(Sqrt[3]))

8π/(3(Sqrt[3]))//N

dodecahedron

The regular polyhedra with the most vertices is the dodecahedron.  Does that work?

Wikipedia's dodecahedron article gives these as the dimensions of a dodecahedron, based on the length of an edge :
 The radius of the sphere that touches ... 
 	vertices is "circumscribed",
 	center of each face is "inscribed",
 	middle of each edge is "midradius".
 Then

rCircumUnscaled = (edge/4)(Sqrt[15]+Sqrt[3]);
rInscribedUnscaled=(edge/20)(Sqrt[250+110Sqrt[5]]);
rMidradiusUnscaled=(edge/4)(3+Sqrt[5]);

My previous definitions set the radius of the inscribed to 1.  Using that scaling,

rCircum=rCircumUnscaled/rInscribedUnscaled;
rMid=rMidradiusUnscaled/rInscribedUnscaled;

{rCircum,rMid}//N

The total post length (if the dodecahedron works) is

20*(rCircum-1)//N

I've installed a package that does some polyhedra stuff; 
see ~/Library/Mathematica/Applications/UniformPolyhedra.m
It has then "wythoff symbol" for dodecahedron as 3,2,5.  (See PolyhedraExamples.m.)
This UniformPolyhedra package definies the coord scale so that the midrange radius is 1,
so 
Then

<<UniformPolyhedra`;
dodec=MakeUniform[w1[3,2,5]];
r=VertexCoordinates[dodec]*rMid;
rHat=r/Norm[r[[1]]];

FaceList[dodec] (* indices into vertices list *)

Length[r]

Graphics3D[dodec]

Abs[Norm[r[[1]]]-rCircum]  (* These should be same : yup.  *)

αDodec=ArcCos[rHat[[1]] . rHat[[2]]]

Here are the cones of light from the 20 dodecahedran vertices.  Yup, they do cover the globe.

dodec picture code

dodecPicture=Graphics3D[{
Gray,Thin,
Table[Line[{origin,rHat[[n]]}],{n,1,20}],
Blue,AbsoluteThickness[3],
Table[Line[{rHat[[n]],r[[n]]}],{n,1,20}],
(*  Transparent,EdgeForm[Green],circle3D[origin,k,1], *)
EdgeForm[Yellow],Yellow,Opacity[0.2],
Table[Cone[{Cos[αDodec]rHat[[n]],r[[n]]},Sin[αDodec]],{n,1,20}],
White,Opacity[0.3],
Sphere[origin,1]
}];

dodec picture

dodecPicture

Turns out there are several interesting things about this coverage that I didn't expect.
	1. Every spot on the globe is illuminated by at least two lights.  And some spots are lit by five.
	2. The light from each tower just reaches three of its neigboring posts.