| [home] - [up] |
Abstract: Kinetic Data Structures (KDS) have now been around for about five years and have given rise to both theoretical and practical developments. This talk will provide a short introduction to KDS, illustrate the concept with a number of examples, and then focus on the more recent work in the field.
A KDS is an algorithmic tool for problems where the goal is to track an attribute of a continuously moving or deforming physical system over time. A KDS succintly summarizes the important aspects of the state of the system in a set of spatial relationships, called certificates, that facilitate or trivialize the computation of the attribute of interest. As the system evolves and certificates fail, a KDS repair mechanism is invoked to update the certificate set and the associated attribute computation. Good KDS design means selecting a certificate set that facilitates the attribute computation, yet is relatively stable and robust under object motion. KDSs have rigorous associated measures of performance and their design shares many qualities with that of classical data structures.
Originally the KDS framework led to new and promising algorithms in virtual reality applications, including collision detection and visibility computations. This talk will quickly survey this work and then focus on some of the newer developments, including applications to physical simulation and ad hoc communication and sensor networks.
Colloquium - 16:00
Abstract: We present a simple combinatorial algorithm for computing the smallest enclosing ball of a set of points Euclidean space. The resulting code is in most cases faster (sometimes significantly) than recent dedicated methods that only deliver approximate results, and it beats off-the-shelf solutions, based on quadratic-programming solvers.
The algorithm resembles the simplex algorithm for linear programming; it comes with a Bland-type rule to avoid cycling in presence of degeneracies and it typically requires very few iterations. We provide a fast and robust floating-point implementation whose efficiency stems from a new dynamic data structure based on dynamic QR-decompositions.
Joint work with Kaspar Fischer and Bernd Gärtner from ETH Zürich.