Thema der Dissertation:
Algorithmic Aspects of Packing Problems Thema der Disputation:
The Complexity Class Ǝℝ and Computational Geometry
Algorithmic Aspects of Packing Problems Thema der Disputation:
The Complexity Class Ǝℝ and Computational Geometry
Abstract: The complexity class Ǝℝ has been named by Schaefer in 2009, first (implicit) hardness- and completeness-results date at least back to the 80’s and 90’s. It turned out that many problems in the field of computational geometry are Ǝℝ-complete, many of whom are related to graph drawing and recognizing members of graph classes. More and more problems from computational geometry are proven to be Ǝℝ-complete, thus the class seems to cover a wide range of somewhat natural problems. Up to today there are at least 7 publications on Ǝℝ and computational geometry in 2021, showing the growing interest in the complexity class.
In this talk, we will formally introduce the complexity class Ǝℝ and give an overview on results related to computational geometry. Then, we exemplary turn to the recent breakthrough result by Abrahamsen, Adamszek, and Miltzow and convey some insights of their Ǝℝ-completeness proof of the art gallery problem.
In this talk, we will formally introduce the complexity class Ǝℝ and give an overview on results related to computational geometry. Then, we exemplary turn to the recent breakthrough result by Abrahamsen, Adamszek, and Miltzow and convey some insights of their Ǝℝ-completeness proof of the art gallery problem.
Zeit & Ort
29.11.2021 | 10:00