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

Online Weight Balancing on the Unit Circle

B

Hiroshi Fujiwara 1(

) , Takahiro Seki 2 , and Toshihiro Fujito 1

1 Toyohashi University of Technology, Toyohashi, Japan
{ h-fujiwara,fujito } @cs.tut.ac.jp
2 Computron Co. Ltd., Maebashi-shi, Japan
[e-mail]

Abstract. We consider a problem as follows: Given unit weights arriv-
ing in an online manner with the total cardinality unknown, upon each
arrival we decide where to place it on the unit circle in R 2 . The objective

is to set the center of mass of the placed weights as close to the origin
as possible. We apply competitive analysis defining the competitive dif-
ference as a performance measure. We first present an optimal strategy
for placing unit weights which achieves a competitive difference of 5 .We
next consider a variant in which the destination of each weight must be
chosen from a set of positions that equally divide the unit circle. We
give a simple strategy whose competitive difference is 0.35. Moreover, in
the oine setting, several conditions for the center of mass to lie at the
origin are derived.

1 Introduction

Suppose that we are given a series of points, each with unit weight, one by one
with the total cardinality unknown in advance. Our task is to place the points
one by one on the unit circle in

2 while keeping a good balance. We are not
allowed to move the point any more, once it is placed. The balance is measured
by the Euclidean distance between the center of mass of the placed points and
the origin.
The diculty is that we do not know how many points will arrive in total.
If we guess the total cardinality somehow at the beginning, then we may try to
place the points, for example, in such a way that they equally divide the unit
circle. If the guess is correct, the center of mass comes to the origin. However, if
the guess fails, say, if one extra point arrives, we have to place it somewhere and
then lose the good balance. Also in the case of fewer points than expected, we
cannot achieve the balance as planned. In this paper we consider this problem
from the viewpoint of competitive analysis .

R

Our Contribution. We apply competitive analysis adopting the competitive dif-
ference as a criterion of competitiveness of a strategy. The competitive difference
is defined as the maximum difference between the cost incurred by the strategy
and the cost incurred by an optimal oine strategy that knows the total cardi-
nality of points in advance. Our results are summarized as follows: