Information Technology Reference
In-Depth Information
Covering a sphere with
n
spherical caps is a well-studied problem (see e.g. [
8
,
11
])
and for many values of
n
, bounds exist on how large the diameter
d
must be
to admit a covering of a sphere of radius
R
.For
n
=
1, a disk
of diameter
d
can wrap an
R
-sphere only if
d
2
ˀR
. This yields
√
x
2
+
x
−
2
2
ˀR
,which
is exactly Upper Bound
2
! This generalization of the antipodal points bound is
most useful when
n
is 1 or 3, where coverings are necessarily very wasteful.
≥
≥
U
pper Boun
d 4.
An
x
×
1
/x
rectangle may wrap an
R
-sphere only if
R
≤
x
2
+(3
x
)
−
2
/ˀ
.
Proof.
Three diameter-
d
disks can wrap an
R
-sphere only if
d
ˀR
(see
s Table
2 of [
11
]).
Composing with the contrapositive of Proposition
3
yields
R
≥
x
2
+(3
x
)
−
2
/ˀ
.
≤
4 Lower Bounds
4.1 Rescaling Lower Bounds on Cubes
Most lower bounds on wrapping take the form of a construction for a specific
x
.
Here we present a method to rescale particular foldings to produce a continuous
set of lower bounds.
Theorem 1.
If
x
×
1
/x
paper wraps an
S
-cube, then there exists a folding of an
x
×
1
/x
rectangle into an
f
(
x
)
-cube where
f
(
x
)=
S
min
x
/x, x/x
}
{
.
Proof.
Suppose
x
<x
. Uniformly scaling an
x
×
1
/x
rectangle by a factor of
x
/x
, yields an
x
×
x
/x
2
rectangle, which wraps an
Sx
/x
-cube. An
x
×
1
/x
rectangle contracts to an
x
×
x
/x
2
rectangle. A corresponding argument can
be made for
x
>x
.
4.2 Rectangle Conversions on Cubes
The rectangle-to-rectangle hinged dissection gadget of [
1
] inspires a technique to
transform wrappings of a particular aspect ratio into general wrappings without
any loss of eciency.
Lower Bound 5.
Any unit-area rectangle wraps a
1
/
6+2
√
2
-cube.
Proof.
The cre
ase pattern in the top-left of Fig.
4
shows a valid wrapping
f
of
a1
/
6+2
√
2-cube from an
x
1
/x
rectangle (fold each horizontal or vertical
crease to a right angle) with these special properties:
×
1. Left and right edges of the paper map to same segment.
2. Left and right halves of the top edge map to the same segment.
3. The bottom edge maps to a point.
Search WWH ::
Custom Search