| [home] - [up] |
Abstract: A set P of points in R^d defines a distance function d by assigning to every point x its least distance to any of the sample points, i.e. d(x)=min_{p \in P} |x-p|. This function is not smooth everywhere, but we can still give meaningful definition of gradients and critical points (local extrema and saddle points). An orbit or flow line of the gradient vectorfield induced by P is a curve that always follows the gradient. We show that the flow lines can be computed efficiently. The stable manifold of a critical point contains all points whose flow line ends in the critical point. The collection of all stable manifolds is cell complex that we call the flow complex. The flow complex turned out to be useful in geometric modeling applications, e.g. surface reconstruction. In the surface reconstruction problem the point set P is a sample from the surface of a solid. The task is compute a manifold model from P that reconstructs that surface as good as possible. Modifying the distance function d gives rise to different flows. We will discuss some modifications that could be useful for bio-geometric modeling, e.g. finding certain cavities in macromolecules, or geometric optimization.
Colloquium - 16:00
Abstract: We present fast algorithms for shortest path problems which are at the core of more complex algorithms for route guidance problems in traffic networks and whose running time is therefore of utmost importance. We model these problems as network flows where one has to solve a Multicommodity Min Cost Flow Problem. Each commodity i corresponds to a given demand d_i, e.g. a user request for a route, and costs on network arcs represent traveling times on these arcs. Formulating this problem as a Linear Program where the variables represent paths in the network, the corresponding separation problem can be interpreted as a (length-bounded) shortest path problem: Find a shortest s_i - t_i path P_i with respect to the dual costs on each arc.
In this setting we are interested in acceleration methods for constrained shortest path computations, like goal-directed and bidirected approaches as well as hierarchical separator approaches. Furthermore we look at possible preprocessings for this problem, like a rectangular decomposition.
Finally some computational results and a framework for implementing these algorithms in a very abstract manner by using generic programming techniques, like templates and traits classes, will be presented.