  The dispersion problem has been widely studied in computational geometry and
facility location, and is closely related to the packing problem. The goal is
to locate n points (e.g., facilities or persons) in a k-dimensional polytope,
so that they are far away from each other and from the boundary of the
polytope. In many real-world scenarios however, the points arrive and depart at
different times, and decisions must be made without knowing future events.
Therefore we study, for the first time in the literature, the online dispersion
problem in Euclidean space.
  There are two natural objectives when time is involved: the all-time
worst-case (ATWC) problem tries to maximize the minimum distance that ever
appears at any time; and the cumulative distance (CD) problem tries to maximize
the integral of the minimum distance throughout the whole time interval.
Interestingly, the online problems are highly non-trivial even on a segment.
For cumulative distance, this remains the case even when the problem is
time-dependent but offline, with all the arriving and departure times given in
advance.
  For the online ATWC problem on a segment, we construct a deterministic
polynomial-time algorithm which is (2ln2+epsilon)-competitive, where epsilon>0
can be arbitrarily small and the algorithm's running time is polynomial in
1/epsilon. We show this algorithm is actually optimal. For the same problem in
a square, we provide a 1.591-competitive algorithm and a 1.183 lower-bound.
Furthermore, for arbitrary k-dimensional polytopes with k>=2, we provide a
2/(1-epsilon)-competitive algorithm and a 7/6 lower-bound. Interestingly, for
the offline CD problem in arbitrary k-dimensional polytopes, we provide a
polynomial-time black-box reduction to the online ATWC problem, and the
resulting competitive ratio increases by a factor of at most 2.
