[Mittagsseminar TI] Mittagsseminar am Dienstag, 6. 8., Donnerstag, 8. 8. und Dienstag, 13. 8.

[Günter Rote <rote@inf.fu-berlin.de>]

Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am

    Dienstag, 6. August 2019, 12:00 Uhr, SR 055, Takustraße 9
    Günter Rote
    zum Thema: Cops and robbers: Monotonicity in graph searching
               (edge search and node search)

und am

    Donnerstag, 8. August 2019, 12:00 Uhr, SR 055, Takustraße 9
    David Wellner (Bachelor-Vortrag, in German)
    zum Thema: Über Dicke und Split-Dicke von Graphen

und am

    Dienstag, 13. August 2019, 12:00 Uhr, SR 055, Takustraße 9
    Tillmann Miltzow (Utrecht)
    zum Thema: Smoothed analysis of order types
               (joint work with Ivor van der Hoog and Martijn van Schaik)

Abstract:
Consider an ordered point set P. Its *order type*, denoted by χ_P, is a map which
assigns to every triple of points a value in {+,-,0} based on whether the points are
collinear (0), oriented clockwise (-) or counter-clockwise (+). An abstract order type
is a map χ from all triples of points to {+,-,0} that satisfies the following condition:
For every set of five elements S⊂{1,…,n} its induced order type χ_S is realizable by
a point set.
Planar point sets are among the most basic and natural geometric objects of study
in Discrete and Computational Geometry. Properties of point sets are relevant
in theory and practice alike. It is known that deciding if an abstract order type is
realizable is complete for the existential theory of the reals. Our results show that
order type realizability is much easier for realistic instances than in the worst case.
In particular, we can recognize instances in "expected NP-time". This is one of the
first ∃R-complete problems analyzed under the lens of Smoothed Analysis.