Information Technology Reference
In-Depth Information
Let us think of
C
θ
(3)
2
as a function of
ʸ
3
with a fixed parameter
ʸ
2
.By
differentiating
C
θ
(3)
2
with respect to
ʸ
3
, we obtain
∂C
θ
(3)
2
∂ʸ
3
2
9
sin
ʸ
3
+
2
2
9
sin
ʸ
3
cos
ʸ
2
=
−
9
sin
ʸ
2
cos
ʸ
3
−
9
sin
ʸ
2
ʸ
3
cos
ʸ
2
=
4
2
−
2
.
This implies that when
ʸ
3
=
ʸ
2
+
ˀ
, the function
C
θ
(3)
2
achieves a minimum of
9
sin
ʸ
2
sin
ʸ
2
+
ˀ
+
2
9
cos
ʸ
2
+
ˀ
cos
ʸ
2
+
2
9
cos
ʸ
2
+
ˀ
+
1
3
2
9
cos
ʸ
2
+
2
2
2
2
1
2
=
1
9
2cos
ʸ
2
2
−
.
(Geometrically speaking, the optimal position of the third point is the midpoint
of the longer arc connecting
P
θ
(1) and
P
θ
(2).) Hence, for general
ʸ
3
,itholds
that
1
=
1
3
1
=
1
1
3
2cos
ʸ
2
2
2
5
5
.
Again by Lemma
1
, we know
C
opt
(3) = 0. Therefore, the competitive difference
is at least
C
θ
(3)
≥
−
−
1
5
.
The strategy
defined below turns out to be optimal. Note that the choice of
placement for the fourth and later points is a matter of taste; any placement
is acceptable as long as the resulting cost does not exceed
θ
1
5
. Here we choose a
placement for the fourth and later points so that the analysis is easy to handle.
See Fig.
1
.
⊧
⊨
0
,
j
=1;
ʱ,
j
=2;
ʸ
j
=
⊩
2
+
ˀ,
j
is odd,
j
≥
3;
2
,
j
is even,
j
≥
4
.
1
5
Lemma 3.
C
(1) = 1
,and
C
(
k
)
≤
for all
k
≥
2
.
θ
θ
Proof.
C
(1) = 1 is trivial. For ease of notation we write
P
(
·
)and
G
(
·
) simply
θ
θ
θ
as
P
(
), respectively. Although the lemma can be proved by explicitly
calculating the coordinate of
G
(
k
) for general
k
·
)and
G
(
·
2, we
he
re give a simpler proof
based
o
n geometric arguments. A
p
plying the strategy
≥
θ
, we calculate
G
(2) =
(
25
,
2
√
6
2
√
6
1
25
). (See
Fig.
1
.)
It
is thu
s observed that the
origin
O
lies on the segment
G
(2)
G
(3) and
OG
(2) =
OG
(3) =
5
. Therefore, the
proof is done if
G
(
k
) lies on the segment
G
(2)
G
(3) for all
k
)and
G
(3) = (
−
25
,
−
25
2.
We begin by proving that every
G
(
k
) is on the line
G
(2)
G
(3), not nece
s
sarily
on that segment. Please note that
P
(3) =
P
(5) =
P
(7) =
≥
2
√
6
5
1
···
=(
−
5
,
−
)and
=(
5
,
2
√
6
5
P
(4) =
P
(6) =
P
(8) =
···
) are on the line
G
(2)
G
(3). For
k
≥
4,
G
(
k
)
Search WWH ::
Custom Search