Kinetic Data Structures in the Black-Box Model

Marcel Roeloffzen

Promotor: prof.dr. M. de Berg (TU/e) and prof.dr. B. Speckmann (TU/e)
Technische Universiteit Eindhoven
Date: 9 October, 2013, 16:00

Summary

Over the course of the years many different structures have been developed for computing and storing geometric information on a set of objects (often points). In recent years there has been a growing interest in maintaining such structures as the input moves over time. The straightforward approach is to recompute the desired structure from scratch whenever the input changes, but this can be wasteful if the changes are small. To avoid unnecessary computations the Kinetic Data Structures (KDS) framework was introduced by Basch, Guibas and Hershberger in 1997. In this framework we assume that the trajectories of the objects are known and we can compute when to change the data structure. This leads to an event-driven approach for which several efficiency guarantees can be proven. Unfortunately, there are many situations when the trajectories are unknown. For example when the input comes from tracking devices, human-controlled avatars in a virtual world or a numerical integrator in a physical simulation. In these cases new locations become available as time progresses and no precise trajectories can be given beforehand. This means we cannot apply the KDS-framework, but we would still like to maintain data structures in a provably efficient manner. For these applications we introduce the black-box model to model the motions of the input and design efficient algorithms to maintain several basic data structures within this model.

In the black-box model we assume that locations of input objects are given at discrete time steps and that between any two time steps each input object moves at most some distance dmax. Without any further knowledge about the distribution of the objects, this maximum displacement dmax does not provide much information. When all objects are very close together we cannot use the information we had about object locations in the previous time step. To cope with these cases we introduce two additional parameters that can be used to analyse our algorithms when the objects are points. The first parameter k denotes the maximum number of points that are contained in any disk (or sphere in higher dimensions) with diameter dmax, that is, k indicates how many points can cluster very closely together. The second parameter spread(k) denotes the k-spread and depends on the first parameter k. The k-spread indicates how far apart the points can be.

In this black-box model we show how to maintain several basic geometric structures on a set of moving points, namely the convex hull, 2-center, Delaunay triangulation and compressed quadtree. The running time of the update algorithms is expressed using the distribution parameters k and spread(k).

For the convex hull and 2-center problem we present a generalized approach that relies on the fact that for some structures not all points are important to compute the structures. Some points may be ignored when updating the structure and, due to the bounded displacement, it may take several time steps before these points have to be considered again. This concept works well for maintaining the convex hull and 2-center. In both cases we provide update algorithms whose running time depends on spread(k) and may even run in sublinear time if the points are nicely (for example uniformly) distributed.

For some structures, such as the Delaunay triangulation or a compressed quadtree, all points are part of the final structure and we cannot apply the above framework. We can however maintain local properties or substructures to ensure that only local updates are necessary in each time step. Due to the bounded displacement we can guarantee that every point influences only a small portion of the structure and, hence, that updates can be done quickly. For the Delaunay triangulation the algorithm itself is a very simple flipping approach that would normally take quadratic time, but with bounded displacement and a nice point distribution is can be as fast as linear. Maintaining a compressed quadtree is also done by maintaining local properties. The algorithm is somewhat more involved, but it is not dependent on the k-spread. The algorithm for maintaining a compressed quadtree can also be adapted to perform collision detection between moving objects in the plane.