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

y

y y

1.0 1.0

1.0

P(14)

P(4)

P(5)

P(2) P(12)

P(6)

P(7) P(3)

P(10)
P(8)

P(3)

0.5 0.5 0.5

P(2)

G(2) G(3)

G(5)
G ( 7 )

G(4) P(6)

P(1)

P( 2 ) P( 1 )

G( 6 )

P(1)

x x x

1.0 0.5 0.5 1.0 1.0 0.5 0.5 1.0 1.0

P(7)

0.5 0.5 1.0

G(5) G(2)

(=G(4)=G(6))

G(3)

P(9)
P(11)

P(7)

P(4)

0.5 0.5 0.5

P(4) P(8)

P(3)

P(5)

P(13)

P(5)

P(6)

P(15)

1.0 1.0 1.0

Fig. 2. Behavior of
theonlinestrategyin
Theorem 2 for the 7-
cyclotomic problem.

Fig. 3. Behavior of
theonlinestrategyin
Theorem 3 for the 8-
cyclotomic problem.

Fig. 4. Behavior of the
oine strategy in Theo-
rem 4 for the 40-cyclotomic
problem, applying p =5.
This figure depicts the
placement of 15 points such
that their center of mass lies
at the origin.

For k = 2, there does not exist such a strategy except for the strategy (0 ,ˀ ).
For k = 3, it is seen that (0 , 2 3 , 4 3 ) is a unique optimal oine strategy. For
k = 4, by a basic manipulation of equations, it is derived that any optimal
strategy has the form (0 ,ˀ,ʸ 3 ,ʸ 3 + ˀ ). Geometrically speaking, C θ (4) = 0 if and
only if P θ (1) P θ (2) P θ (3) P θ (4) forms a rectangle.
What if k = 5? Apparently, the strategy (0 , 2 5 , 4 5 , 6 5 , 8 5 ), which forms a
regular pentagon, is optimal. We also have (0 ,ˀ,ʸ 3 ,ʸ 3 + 2 3 ,ʸ 3 + 4 3 ), for which
the points compose a diameter and a regular triangle. Note that since the center
of mass of a diameter and that of a regular triangle lie both at the origin, the
center of mass of the five points lies at the origin as well. Then, is there any
strategy that satisfies C θ (5) = 0 but does not form either a regular pentagon or
the combination of a diameter and a regular triangle? The answer is yes. For 5

>

ʵ> 0, we can choose ʴ> 0 such that the strategy (0 , 2 5 ʴ, 4 5 + ʵ, 6 5 ʵ, 8 5 − − + ʴ )

has a cost of zero.

4 n -Cyclotomic Problem

4.1 Simple Online Strategy

For each of the cases of odd n and even n , we provide a simple strategy and
analyze its competitive difference. We will later explain that our strategy is not
optimal in general. See Figs. 2 and 3 for the behavior.

Theorem 2. For the n -cyclotomic problem with odd n ( ≥ 3) , the strategy θ

defined as

ʸ j = ( j

− 1)( n − 1) ˀ

, 1 ≤ j ≤ n

n