|
|
Institute of Geometry |
| Contact People Courses & Exams Events Research Lehramtsstudium |
Die Vorträge finden statt entweder im Seminarraum 2 des Instituts f. Geometrie (Kopernikusgasse 24, 4. Stock, 8010 Graz) oder im Seminarraum des Instituts f. Statistik (Kopernikusgasse 24, 3. Stock, 8010 Graz).
| 2015-01-20 | |
| 9:00 SR Geometrie |
Wolfgang Mulzer (FU Berlin)
New Algorithms for Two Classic Problems from Computational Geometry. |
| Abstract: First, I will consider the problem of finding the Delaunay triangulation of
a planar point set. Delaunay triangulations have a rich and long history,
and they are ubiquitous in computational geometry. Optimal comparison-based
algorithms for computing them have been known for a long time. However,
once we go beyond the comparison model, much less is known. In 2000, Willard
asked whether transdichotomous methods, that allow direct manipulation of
bits, could be used in the context of Delauany triangulations. I will show
that this is indeed the case and describe an algorithm that finds the
Delaunay triangulation in the same time bound as for integer sorting.
Second, I will talk about computing the Frechet distance between two planar polygonal chains. The Frechet distance is a popular distance measure for curves with many practical applications. However, the first algorithm for computing the Frechet distance by Alt and Godau was not improved for almost 20 years. I will show how to use a variant of the Four-Russians trick to obtain a faster algorithm for the problem. — Based on joint work with K. Buchin, M. Buchin, and W. Meulemans. | |
| 13:00 SR Geometrie |
Adrian Dumitrescu (U. Wisconsin-Milwaukee)
Opaque barriers for convex domains. |
| Abstract:
The problem of finding a collection of curves of minimum total length that
meet all the lines intersecting a given planar convex body was initiated by
Mazurkiewicz in 1916. Such a collection forms an opaque barrier
for the convex body. We consider the problem of computing the shortest
barrier for a given convex polygon with n vertices. No exact
algorithm is currently known even for the simplest instances such as a
square or an equilateral triangle.
For arbitrary (possibly disconnected) barriers, we present an
approximation algorithm with ratio
1/2 + 2+√2/π=1.5867...
For connected barriers we achieve the approximation ratio 1.5716,
while for single-arc barriers we achieve the approximation ratio
π+5/π+2 = 1.5834... All three algorithms run in O(n) time.
We also show that if the barrier is restricted to the
(interior and the boundary of the)
input polygon, then the problem admits a fully
polynomial-time approximation scheme for the connected case and a
quadratic-time exact algorithm for the single-arc case.
In 1991 Shermer proposed an exponential-time algorithm that computes a
(possibly disconnected) interior barrier made of segments for any
given convex n-gon. Recently, it was shown by Provan et al.
that this barrier is not always the shortest. Here we give a Shermer-like
algorithm that computes an interior polygonal barrier whose length is
at most 1.7168 times the optimal and that runs in O(n) time.
— Based on separate pieces of joint work with Minghui Jiang (USU), János Pach (EPFL), and Csaba Tóth (California State Univ., Northridge | |
| 16:00 SR Geometrie |
Stefan Huber (ISTA)
Skeleton Structures in Computational Geometry. |
| Abstract: The skeleton of a shape is a retraction of the shape of (at least) co-dimension 1. A prime example is the medial axis, which consists of all loci within the shape whose infimum distance to the boundary of the shape is attained at two or more points. In computational geometry, skeletons are a versatile tool to solve numerous algorithmic problems in a geometric and topological setting, such as capturing the local thickness of a shape, robot-motion planing or computing different types of offset curves. In this talk we will survey two specific skeletons, namely the Voronoi diagram and the straight skeleton, from an algorithmic, geometric and applied perspective. | |
| 2015-01-21 | |
| 9:00 SR Geometrie |
Bruno Benedetti (FU Berlin)
Discrete Morse Theory and modern algorithmic approaches to topology. |
| Abstract: Simplicial complexes provide a general approach to the study of
differential geometry and algebraic topology. Discrete Morse Theory is a
technique that enables a simplicial complex to be "simplified" through a
sequence of reductions. Purely geometric tools, like knot theory,
differential geometry, and hyperbolic geometry, have allowed us to obtain
both positive results (e.g., certificates that some reduction sequences
exist) and negative results (e.g., obstructions to the existence of any
reduction).
On the applied side, an advantage of discrete geometry over continuous geometry is the possibility to leverage computational tools. Discrete Morse theory is the basis for fast (co)reduction techniques that are used in modern software for homology computations. I will sketch our algorithms for producing a Discrete Morse vector quickly, thereby proposing a "measure of complicatedness" for triangulations. If time permits, I will conclude by sketching algorithmic approaches to old open problems in PL topology, like the Zeeman conjecture, or a conjecture by Oliver we recently solved. (This is partly joint work with Karim Adiprasito and Frank Lutz.) | |
| 13:30 SR Statistik |
Mikael Vejdemo-Johansson (KTH Stockholm)
Intrinsic circle-valued coordinates - theory and applications. |
| Abstract:
A classical theorem in algebraic topology produces a constructive bijection
between dimension 1 cohomology classes and functions from a topological
space to the circle. In this talk, I will describe this connection, how
persistence can be adapted to produce intrinsic and data-driven coordinate
functions with a measure of quality for the computed coordinate, and some
applications of these methods.
In particular, I will trace the development of persistent cohomology and circle-valued coordinates (joint work with Vin de Silva and Dmitriy Morozov); and then display applications of the coordinate work to analysing weather signals, analysing motion capture of gaits (joint work with Primoz Skraba, Danica Kragic and Florian Pokorny). Finally, I will present some speculative ideas for adapting these methods to an online/streaming learning setting — where for instance gait models can be learned directly from data using cohomological coordinates over time as more and more data is measured from a walking subject. | |
| 2015-01-22 | |
| 9:30 SR Statistik |
Frank Lutz (TU Berlin)
Computational Topology of Materials. |
| Abstract: Polycrystalline materials, such as metals, are composed of crystal
grains of varying size and shape. Typically, the occuring grain cells
have the combinatorial types of 3-dimensional simple polytopes,
and together they tile 3-dimensional space. We will observe that
the frequent grain types are "combinatorially round" -- which
gives us a new starting point for the mircostructure analysis of steel.
Computational homology packages such as CHomP or Perseus allow to obtain homological information for large complexes from material sciences or other. These packages extensively use (NP-hard) discrete Morse theory as a (fast) preprocessing step to avoid (slow, polynomial time) Smith Normal Form computations. In fact, it is surprisingly hard to construct "complicated" examples on which homology calculations perform poorly. We present an interesting infinite series of such complicated triangulations, based on the Akbulut-Kirby 4-spheres and related to the smooth 4-dimensional Poincaré conjecture and the Andrews-Curtis conjecture. | |
| 13:30 SR Geometrie |
Pawel Pilarczyk (ISTA)
Automatic classification of global dynamics in multi-parameter systems. A topological approach.. |
| Abstract: A computational framework will be introduced for automatic classification of global dynamics in a discrete-time semi-dynamical system depending on a few parameters. The method is based on Conley's topological approach to dynamics: The phase space is split into a Morse decomposition, in which Morse sets contain all the recurrent dynamics present in the system, and the dynamics in the remainder of the space is gradient-like. This decomposition is computed by subdividing the phase space into a grid, representing the map by means of a multivalued mapping of grid elements, and applying efficient graph algorithms to identify an outer enclosure for a Morse decomposition. The Conley index, an algebraic-topological invariant that can be computed effectively in this setting, provides additional information about the Morse sets. Interval arithmetic is involved in the numerics, and allows to conduct the computation for small intervals of parameters at one fell swoop. The space of parameters is split into classes with equivalent dynamics related by continuation of the Morse decompositions. This method provides mathematically rigorous information on the system (a.k.a. computer-assisted proof). Thanks to mild assumptions on the dynamical system, the method has a potential for wide applicability. | |
| 2015-01-23 | |
| 9:00 SR Statistik |
Michael Kerber (MPI Saarbrücken)
The Persistent Homology Pipeline: Shapes, Computations, and Applications. |
| Abstract: The theory of persistent homology provides
a multi-scale summary of homological features for a given data set
and this summary is stable with respect to noise. These properties
make homological algebra applicable to a
growing range of application areas and give rise to the
field of topological data analysis.
This success of linking theory and applications has posed the challenge
of computing persistence on large data sets. Typical questions
in this context are: How can we efficiently build combinatorial cell complexes
out of point cloud data? How can we compute the persistence summaries
of very large cell complexes in a scalable way? Finally, how does the computed
summary lead us to new insights into the considered application?
My talk will focus on two results in this context: I will introduce a simple heuristic for computing persistent homology that significantly accelerates the running time in practice and has led to the first practically efficient implementation on distributed platforms. Secondly, I will present a technique to approximate Cech complexes through significantly smaller cell complexes, connecting the problem to approximation algorithms from computational geometry. | |
| 13:00 SR Statistik |
Paweł Dłotko (Univ. Pennsylvania)
Computational and applied topology: from continuous to discrete. |
| Abstract: In this talk I will discuss one possible connection between a continuous and a discrete mathematics. By using ideas from rigorous numerics I will provide an algorithm to construct a regular CW complex having the same homotopy type as a sublevel set of a given, sufficiently smooth, function restricted to a compact rectangle. Later I will discuss how to use the data structure developed in the construction of the mentioned CW-complex for a rigorous computation of persistent homology. The input parameters for that computations are: an error tolerance, a continuous function and a compact rectangular domain in which the persistence will be computed. As an output, a persistence homology of the input function on the considered domain will be provided. I will show that the resulting diagram will be not further than the assumed error bound away from the true persistence diagram of the function on the domain. At the end I will give some examples showing how the presented algorithms allows to use topological data analysis techniques along with standard numerical analysis techniques. |