Algorithmic Tools for Proximity Problems among Curves

In recent years, a vast amount of data has become available that can be broadly characterized as path or trajectory records. The data comes from a variety of sources, as different as motion capture of actors, flight paths of birds, bus routes, traces of taxi trips, sports analysis, GPS sensors 011 cattle, and stock performance recordings. Recent advancements of technology, such as the proliferation of GPS—enabled mobile phones. makes such data sources ubiquitous. This gives rise to several challenges, such as storing the data, identifying and removing redundancies, clustering it, and preprocessing it to facilitate a variety of common and useful queries.

Consequently, we are witnessing an outburst of research surrounding path and trajectory data. Much of it is experimental, with little focus on the guaranteed performance, in terms of time, storage, and quality, of the various heuristics used for processing the sea of data. In this proposal, we are interested in designing effective algorithms and data structures with provable performance guarantees for fundamental problems dealing with path and trajectory data. We will concentrate our attention on proximity problems, including nearest—neighbor searching, clustering, and their relatives. However, in contrast with much of the previous related research, we intend to put special emphasis 011 the usefulness of our results, by taking into account properties that are often found in real—life inputs. We will also consider these problems in the streaming model, which often suits the circumstances in practice.