23 citations · 25 across the 6 of their papers we have counts for
5 papers · 1 filter
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…
NP-membership for the boundary-boundary art-gallery problem
Jack Stade
The boundary-boundary art-gallery problem asks, given a polygon representing an art-gallery, for a minimal set of guards that can see the entire boundary of (the wall of th…
Two Tiling is Undecidable
Jack Stade
We show that the following problem is undecidable: given two polygonal prototiles, determine whether the plane can be tiled with rotated and translated copies of them. This improve…
The Point-Boundary Art Gallery Problem is -hard
Jack Stade
We resolve the complexity of the point-boundary variant of the art gallery problem, showing that it is -complete, meaning that it is equivalent under polynomial…
Topological Universality of the Art Gallery Problem
Jack Stade, Jamie Tucker-Foltz
We prove that any compact semi-algebraic set is homeomorphic to the solution space of some art gallery problem. Previous works have established similar universality theorems, but h…