Abstract. The problem of maintaining geometric structures for points in motion has been well studied over the years. The vast majority of theoretical work in this area has been based on the assumption that point motion is continuous and the future motions of the points are known in advance. In practice, however, motion is typically presented incrementally in discrete time steps and the long-term motion of points is not known and may not even be predictable. We consider the problem of maintaining a data structure for storing a set of points under such incremental motion. We present a simple online model in which two agents cooperate to maintain the structure. One defines the data structure and provides a collection of certificates, which guarantee the structure's correctness. The other checks that the motion over time satisfies these certificates and notifies the first agent of any violations. We present efficient online algorithms for maintaining both nets and net trees for a point set undergoing incremental motion. We analyze our algorithms' efficiency by bounding their competitive ratios relative to an optimal algorithm. Our competitive ratio is a function of the doubling dimension of the space and (in the case of the net tree) the height of the net tree.
They further presented a simple online model in which two agents named observer and builder cooperated to maintain the incremental motion REF .
Maintaining nets and net trees under incremental motion
In Proc. 20th Annu. Internat. Sympos. Algorithms Comput
Computer Science