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

1

(a) We present a non-trivial optimal strategy whose competitive difference is

5 .
This means that according to our strategy, the cost is guaranteed to be at
most the optimal oine cost plus

1

5 .
(b) We impose the n -cyclotomic constraint on the problem that for fixed n ,the
destination of each point has to be chosen from (cos 2 k n , sin 2 k n { ) | 0 ≤ k ≤

n and each position is occupied by at most one point. Depending

on the parity of n , we give a simple and competitive strategy. Our strategy
guarantees a competitive difference of 0.35 for odd n and

− 1 ,k ∈ Z }

1

3 for even n .
(c) We investigate the n -cyclotomic constrained problem in the oine setting, in
which the cardinality of points is informed at the beginning. Even with the
information of the cardinality, it is not clear whether there is a placement
of points that lets the center of mass come exactly to the origin. We reveal
several conditions for the existence of such a placement.

Related Work. To the best of our knowledge, this paper seems the first to focus
on the placement of weighted objects that arrive in an online manner in terms
of the optimal placement of their center of mass. One can find many studies
with similar purposes in the oine setting: Kurebe et al. [ 6 ] considered the
placement of weighted rectangles on

2 to let their center of mass approach
the target position. Teramoto et al. [ 7 ] studied the insertion of points into the
unit square in

R

d in such a way that the Euclidean distance between any pair
of points becomes as uniform as possible. Recently, Barba et al. [ 1 ] considered
the problem that given a set of weights, a closed connected region, and a target
position, we are asked to place the weights on the boundary of the region so that
the center of mass lies at the target.
In consistent hashing, one can think that items and caching machines are
both mapped to points on the unit circle [ 4 , 5 ]. In the context of the space
science, satellite constellation design for covering the Earth's sphere has been of
great interest, for example [ 3 , 9 ].

R

2 Problem Statement and Preliminaries

Throughout this paper a point denotes an individual object that is to be placed
(or has been placed) on

2 , while a position stands for where to place a point

R

2 . Each point has unit weight unless we specify otherwise. We sometimes
iden tify a position on

on R

2 and its xy coordinate, such as the origin O =(0 , 0).
AB denotes the Euclidean distance between the positions A and B .
We define the online weight balancing problem as follows. We are given a
series of points, each with unit weight, in an online manner where the points
arrive one by one and the total cardinality is unknown in advance. Our task is
to place each point, upon its arrival, somewhere on the unit circle in

R

2 . Once
a point is placed, it cannot be moved any more. The objective is to minimize
the cost which is defined as the Euclidean distance between the center of mass
of the placed points and the origin, that is, the center of the unit circle.

R