1 citations · 1 across the 7 of their papers we have counts for
4 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…
Clustering with Few Disks to Minimize the Sum of Radii
Mikkel Abrahamsen, Sarita de Berg, Lucas Meijer +2
Given a set of points in the Euclidean plane, the -MinSumRadius problem asks to cover this point set using disks with the objective of minimizing the sum of the radii of…
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…