11 citations · 60 across the 20 of their papers we have counts for
5 papers · 1 filter
Range-Clustering Queries
Mikkel Abrahamsen, Mark de Berg, Kevin Buchin +2
In a geometric -clustering problem the goal is to partition a set of points in into subsets such that a certain cost function of the clustering is minimized.…
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…
Minimum Perimeter-Sum Partitions in the Plane
Mikkel Abrahamsen, Mark de Berg, Kevin Buchin +2
Let be a set of points in the plane. We consider the problem of partitioning into two subsets and such that the sum of the perimeters of an…
Best Laid Plans of Lions and Men
Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg +1
We study the following question dating back to J.E. Littlewood (1885-1977): Can two lions catch a man in a bounded area with rectifiable lakes? The lions and the man are all assume…
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…