Algorithms for Large Dynamic Geometric Graphs

Goals

The goal of this project is to develop methods for the analysis and processing of large dynamic graphs, which arise among others in applications of computer graphics and in mobile ad-hoc networks. We consider dynamics primarily to be dynamics which are induced by motion. Furthermore, we assume that those graphs do not fit into main memory due to there tremendous size. Therefore, even linear time algorithms are unacceptable slow on this kind of input. The maintenance of data-structures is also inefficient due to the dynamics induced by motion. Therefore, in this project we develop and analyze methods for gathering information about this kind of large geometric graphs in sub-linear time. In the first phase of the project, we focussed on developing and analyzing methods for calculating information about those graphs in sub-linear time, where we primarily developed algorithms for Property Testing in graphs. In the second phase of the project, our work focussed on the development of sub-linear approximation algorithms for basic graph problems like the calculation of minimal spanning trees or clustering problems.

Another main focus of our project is modelling and complexity of motion. We investigate motion especially on examples from computer graphics: Due to mobile parts of a 3D scene as well as the motion of possibly several visitors in the spirit of a walkthrough system, the order of 2D-views of the 3D scene, that have to be rendered in real-time, is highly dynamic. Thus classical static methods are not promising any more. Therefore, we need methods that support the rendering process, without maintaining complex data structures. Especially on-line methods are well suited for this kind of application.

Currently we mainly investigate issues in the area of "sub-linear algorithms for problems on large graphs" as well as "data structures and algorithms for moving objects". In both parts we focus on the development of algorithms for clustering problems. Such clustering techniques can be applied to structure (mobile) networks as well as in the development of data structures for problems in computer graphics.

Sub-linear algorithms for problems on large graphs

The research area of "sub-linear algorithms" is still quite young. That is probably the reason for the fact that there are only few results known about classes of problems for which sub-linear algorithms do exist. In the area of sub-linear approximation algorithms there is not a single result like this known to us. The known algorithms base on methods, that are specially fitted for the problem at hand and are hard to transfer to other related problems. Therefore we are convinced, that developing more general methods for sub-linear algorithms is a central goal of research within this area. In order to approach this goal, we will already investigate single selected problems in the second period of the proposal. We will focus on classical clustering algorithms like k-median, k-means and min-sum-k-clustering.

Data structures and algorithms for moving objects

An important goal of our project is the modelling and the development of algorithms for moving objects. We are especially interested in applications with high dynamics. To handle those dynamics, we plan to apply techniques from the area of sub-linear algorithms.

The goal of the third phase of the proposal is the development of clustering algorithms for moving objects. This kind of algorithms have applications in mobile ad-hoc networks and in computer graphics. We will concentrate on the two theoretical models of kinetic and soft kinetic data structures as well as on applications from computer graphics. There we want to consider the smoothed motion complexity - a measures of complexity developed within this project.

The project is funded since the 1.1.2002 by the DFG (German Research Society) within the scope of the priority programme "algorithmic of large and complex networks".