11 citations · 119 across the 41 of their papers we have counts for
29 papers · 1 filter
The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem
Lucas Meijer, Till Miltzow, Johanna Ockenfels +1
In the (Nesting) Bird Box Problem we are given a polygonal domain P and a number k and we want to know if there is a set B of k points inside P such that no two points in B can see…
Devil's Games and : Continuous Games complete for the First-Order Theory of the Reals
Lucas Meijer, Arnaud de Mesmay, Tillmann Miltzow +2
We introduce the complexity class Quantified Reals (). Let FOTR be the set of true sentences in the first-order theory of the reals. A language is in $\text…
Recognition of Unit Segment and Polyline Graphs is -Complete
Michael Hoffmann, Tillmann Miltzow, Simon Weber +1
Given a set of objects in the plane, the corresponding intersection graph is defined as follows. Each object defines a vertex and an edge joins two vertices whenever the corres…
Geometric Thickness of Multigraphs is -complete
Henry Förster, Philipp Kindermann, Tillmann Miltzow +3
We say that a (multi)graph has geometric thickness if there exists a straight-line drawing and a -coloring of its edges where no…
Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain
Sarita de Berg, Tillmann Miltzow, Frank Staals
We devise a data structure that can answer shortest path queries for two query points in a polygonal domain on vertices. For any , the space complexity of…
The Complexity of Recognizing Geometric Hypergraphs
Daniel Bertschinger, Nicolas El Maalouly, Linda Kleist +2
As set systems, hypergraphs are omnipresent and have various representations ranging from Euler and Venn diagrams to contact representations. In a geometric representation of a hyp…
Sometimes Two Irrational Guards are Needed
Lucas Meijer, Tillmann Miltzow
In the art gallery problem, we are given a closed polygon , with rational coordinates and an integer . We are asked whether it is possible to find a set (of guards) of si…
The Complexity of the Hausdorff Distance
Paul Jungeblut, Linda Kleist, Tillmann Miltzow
We investigate the computational complexity of computing the Hausdorff distance. Specifically, we show that the decision problem of whether the Hausdorff distance of two semi-algeb…
Topological Art in Simple Galleries
Daniel Bertschinger, Nicolas El Maalouly, Tillmann Miltzow +2
Let be a simple polygon, then the art gallery problem is looking for a minimum set of points (guards) that can see every point in . We say two points can see each…
Chasing Puppies: Mobile Beacon Routing on Closed Curves
Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna +5
We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others' work on beacon-based routing. Consider a human and a puppy on a simple closed curve…
Local Complexity of Polygons
Fabian Klute, Meghana M. Reddy, Tillmann Miltzow
Many problems in Discrete and Computational Geometry deal with simple polygons or polygonal regions. Many algorithms and data-structures perform considerably faster, if the underly…
Between Shapes, Using the Hausdorff Distance
Marc van Kreveld, Tillmann Miltzow, Tim Ophelders +2
Given two shapes and in the plane with Hausdorff distance , is there a shape with Hausdorff distance to and from and ? The answer is always yes, and dep…
A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
Simon Hengeveld, Tillmann Miltzow
Given a closed simple polygon , we say two points see each other if the segment is fully contained in . The art gallery problem seeks a minimum size set $G\subset…
Framework for -Completeness of Two-Dimensional Packing Problems
Mikkel Abrahamsen, Tillmann Miltzow, Nadja Seiferth
The aim in packing problems is to decide if a given set of pieces can be placed inside a given container. A packing problem is defined by the types of pieces and containers to be h…
Maximum Clique in Disk-Like Intersection Graphs
Édouard Bonnet, Nicolas Grelier, Tillmann Miltzow
We study the complexity of Maximum Clique in intersection graphs of convex objects in the plane. On the algorithmic side, we extend the polynomial-time algorithm for unit disks [Cl…
Smoothing the gap between NP and ER
Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow
We study algorithmic problems that belong to the complexity class of the existential theory of the reals (ER). A problem is ER-complete if it is as hard as the problem ETR and if i…
A Universality Theorem for Nested Polytopes
Michael G. Dobbins, Andreas Holmsen, Tillmann Miltzow
In a nutshell, we show that polynomials and nested polytopes are topological, algebraic and algorithmically equivalent. Given two polytops and a number , the Nest…
Smoothed Analysis of Order Types
Ivor van der Hoog, Tillmann Miltzow, Martijn van Schaik
Consider an ordered point set , its order type (denoted by ) is a map which assigns to every triple of points a value in based on whether the…
On the VC-dimension of half-spaces with respect to convex sets
Nicolas Grelier, Saeed Gh. Ilchi, Tillmann Miltzow +1
A family S of convex sets in the plane defines a hypergraph H = (S, E) as follows. Every subfamily S' of S defines a hyperedge of H if and only if there exists a halfspace h that f…
Smoothed Analysis of the Art Gallery Problem
Michael Gene Dobbins, Andreas Holmsen, Tillmann Miltzow
In the Art Gallery Problem we are given a polygon on vertices and a number . We want to find a guard set of size , such that each point in is s…
Completeness for the Complexity Class and Area-Universality
Michael G. Dobbins, Linda Kleist, Tillmann Miltzow +1
Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class plays a crucial role in the study of geometric problems.…
The Art Gallery Problem is -complete
Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow
We prove that the art gallery problem is equivalent under polynomial time reductions to deciding whether a system of polynomial equations over the real numbers has a solution. The…
Irrational Guards are Sometimes Needed
Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow
In this paper we study the art gallery problem, which is one of the fundamental problems in computational geometry. The objective is to place a minimum number of guards inside a si…
An Approximation Algorithm for the Art Gallery Problem
Édouard Bonnet, Tillmann Miltzow
Given a simple polygon on vertices, two points in are said to be visible to each other if the line segment between and is contained in…