New data structures and algorithms for mobile data
Mohammad Ali Abam · TU/e Research Portal · 2007
Recent advances in sensing and tracking technology have led researchers to investigate the problem of designing and analyzing algorithms and data structures for moving objects. One important issue in this area of research is which assumptions are made about the motions of the objects. The most common model is one where motions are assumed to be continuous and explicitly known in advance (or at least in the near future), usually as polynomial functions of time. The kinetic-data-structure framework introduced by Basch et al. is based on this model. It has become the common model for dealing with moving objects in computational geometry. A kinetic data structure (KDS) maintains a discrete attribute of a set of moving objects— the convex hull, for instance, or the closest pair. The basic idea is that although all objects move continuously there are only certain discrete moments in time when the combinatorial structure of the attribute—the ordered set of convex-hull vertices, or the pair that is closest—changes. A KDS contains a set of certificates that constitutes a proof that the maintained structure is correct. These certificates are inserted in a priority queue based on their time of expiration. The KDS then performs an event-driven simulation of the motion of the objects, updating the structure whenever an event happens, that is, when a certificate fails. In some applications, continuous tracking of a geometric attribute may be more than is needed; the attribute is only needed at certain times. This leads us to view a KDS as a query structure: we want to maintain a set S of moving objects in such a way that we can reconstruct the attribute of interest efficiently whenever this is called for. This makes it possible to reduce the maintenance cost, as it is no longer necessary to update the KDS whenever the attribute changes. On the other hand, a reduction in maintenance cost will have an impact on the query time, that is, the time needed to reconstruct the attribute. Thus there is a trade-off between maintenance cost and query time. In Chapter 2, we show a lower bound for the kinetic sorting problem showing the following: with a subquadratic maintenance cost one cannot obtain any significant speed-up on the time needed to generate the sorted list (compared to the trivial O(n log n) time), even for linear motions. This negative result gives a strong indication that good trade-offs are not possible for a large number of geometric problems—Voronoi diagrams and Delaunay triangulations, for example, or convex hulls—as the sorting problem can often be reduced to such problems. KDSs form a beautiful framework from a theoretical point of view, but whether or not they perform well in practice is unclear. A serious problem for the applicability of the KDS framework in practice is how to cope with the situation where event times cannot be computed exactly and events may be processed in a wrong order. We addresses this problem in Chapter 3. We present KDSs that are robust against the out-of-order processing, including kinetic sorting and kinetic tournaments. Our algorithms are quasi-robust in the sense that the maintained attribute of the moving objects will be correct for most of the time, and when it is incorrect, it will not be far from the correct attribute. The aim of the KDS framework is not only maintaining a uniquely defined geometric attribute but also maintaining a query data structure in order to quickly answer queries involving objects in motion such as "Which are the points currently inside a query rectangle?", or "What is currently the nearest point to a given query point?". In Chapter 4, we study the kinetic maintenance of kd-trees which are practical data structures to quickly report all points inside any given region. We present a new and simple variant of the standard kd-tree, called rank-based kd-trees, for a set of n points in d-dimensional space. Our rank-based kd-tree supports orthogonal range searching in time O(n1-1/d+k) and it uses O(n) storage—just like the original. But additionally it can be kinetized easily and efficiently. We obtain the similar results for longest-side kd-trees. Collision detection is a basic problem arising in all areas of geometric modeling involving objects in motion—motion planning, computer-simulated environments, or virtual prototyping, to name a few. Kinetic methods are naturally applicable to this problem. Although most applications of collision detection are more concerned with three dimensions than two dimensions, so far KDSs have been mostly developed for two-dimensional settings. In Chapter 5, we develop KDSs for 3D collision detection that have a near-linear number of certificates for multiple convex fat objects of varying sizes and for a special case of balls rolling on a plane. In a practical setting, the object motion may not known exactly or the explicit description of the motion may be unknown in advance. For instance, suppose we are tracking one, or maybe many, moving objects. Each object is equipped with a device that is transmitting its position at certain times. Then, we just have access to some sample points of the object path instead of the whole path, and an explicit motion description is unavailable. Thus, we are just receiving a stream of data points that describes the path along which the object moves. This model is the subject of Chapter 6. Here, we present the first general algorithm for maintaining a simplification of the trajectory of a moving object in this model, without using too much storage. We analyze the competitive ratio of our algorithms, allowing resource augmentation: we let our algorithm maintain a simplification with 2k (internal) points, and compare the error of our simplification to the error of the optimal simplification with k points.