[home] - [up] |
Abstract: Algorithms and data structures for long-running simulations or continuous monitoring applications do not always fit into the style of big-O asymptotic analysis that is based on batch processing (input, processing, output). The alternatives of amortized analysis, competitive analysis, or experimental evaluation do not always suit. Amortized analysis can hide unacceptably large per-operation costs, competitive analysis is difficult even on well-established algorithms like LRU page replacement, and experimental evaluations are difficult to compare and can obscure the portable ideas and concepts with non-portable implementation details. For this reason, the "Kinetic Data Structures" (KDS) framework, which supports the design and analysis of algorithms and data structures that monitor properties of data in motion, is an exciting development in computational geometry.
In this lecture we will first give an introduction to Kinetic Data Structures and then describe in detail a KDS for collision detection between simple polygons.
Colloquium - 16:00
Abstract: A finite Coxeter group acting on some euclidean space determines a polytope, namely the convex hull of all the matrices that define the action. A certain set of rank one matrices associated with the action, the Birkhoff tensors, are known to be facet normals of these polytopes. It has been conjectured that in the case where the Coxeter group has an unbranched Coxeter graph, the Birkhoff tensors constitute all facet normals. For example, a special case of the conjecture amounts to the well known Birkhoff-von Neumann theorem. In this talk I will introduce the problem, show some examples, and present some ideas of how this conjecture might be solved in a classification free proof. This is joint work with Vic Reiner.