11 citations · 119 across the 41 of their papers we have counts for
3 papers · 1 filter
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…