15 citations · 45 across the 12 of their papers we have counts for
3 papers · 1 filter
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…
Approximation Schemes for Independent Set and Sparse Subsets of Polygons
Anna Adamaszek, Sariel Har-Peled, Andreas Wiese
We present an -approximation algorithm with quasi-polynomial running time for computing the maximum weight independent set of polygons out of a given set of polygo…
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…