Online Weight Balancing on the Unit Circle - Discrete and Computational Geometry and Graphs - page 68

3 Basic Problem

3.1 Optimal Online Strategy

We first show a lower bound on the competitive difference and then give a
strategy whose competitive difference coincides with that value. We begin by
presenting a simple lemma on the oine cost.

Lemma 1. For the basic problem, it holds that
C opt ( k )= 1 ,k =1;
0 ,k ≥ 2 .

Proof. It is trivial that C opt (1) = 1 since the cost is one wherever we place a
single point. For k 2, just adopt the strategy (0 , 2 k , 4 k ,..., 2( k − 1) ˀ ≥ ).

k

By rotational symmetry, we can assume that an optimal strategy satisfies ʸ 1 =0
and 0

157 ⓦ ), which is a key angle for obtaining
an optimal strategy. The next lemma gives a lower bound on the competitive
difference.

ˀ .Let ʱ := 2 arccos 5

≤ ʸ 2 ≤ ( ≈

Lemma 2. Any strategy for the basic problem has a competitive difference of at
least

1

5 .

Proof. Fix a strategy θ arbitrarily. By rotational symmetry, we can assume that

ʸ 1 =0and0 ≤ ʸ 2 ≤ ˀ . We will show that the competitive difference is at least

1
5

regardless of the value of ʸ 2 .
(i) Case 0 ≤ ʸ 2 <ʱ .Wehave

G θ (2) := 1

2 sin ʸ 2 . 2 (1 + cos ʸ 2 ) , 1

cos 2

Since x → is a decreasing function on [0 ,ˀ ],

(1 + cos ʸ 2 ) 2 +sin 2 ʸ 2 =cos ʸ 2
2

C θ (2) = 1
2

> cos ʱ
2

= 1

5 .

On the other hand, C opt (2) = 0 by Lemma 1 . Therefore, the competitive differ-
ence is greater than

1

5 .

ʸ 2 <ˀ . We evaluate the cost after the third point has been
placed. For ease of analysis, we square the cost:

(ii) Case ʱ ≤

C θ (3) 2 = 1
3

cos ʸ j 2 + 1

3

sin ʸ j 2

3 3

j =1 j =1

= 2

9 sin ʸ 2 sin ʸ 3 + 2 9 cos ʸ 3 cos ʸ 2 + 2 9 cos ʸ 2 + 2 9 cos ʸ 3 + 1 3 .