6 citations · 12 across the 4 of their papers we have counts for
11 papers
Geometric Embeddability of Complexes is -complete
Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow
We show that the decision problem of determining whether a given (abstract simplicial) -complex has a geometric embedding in is complete for the Existential Theory…
Covering Polygons is Even Harder
Mikkel Abrahamsen
In the MINIMUM CONVEX COVER (MCC) problem, we are given a simple polygon and an integer , and the question is if there exist convex polygons whose union is $\ma…
Chasing Puppies: Mobile Beacon Routing on Closed Curves
Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna +5
We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others' work on beacon-based routing. Consider a human and a puppy on a simple closed curve…
Online Packing to Minimize Area or Perimeter
Mikkel Abrahamsen, Lorenzo Beretta
We consider online packing problems where we get a stream of axis-parallel rectangles. The rectangles have to be placed in the plane without overlapping, and each rectangle must be…
Escaping an Infinitude of Lions
Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg +1
We consider the following game played in the Euclidean plane: There is any countable set of unit speed lions and one fast man who can run with speed for some value…
Tiling with Squares and Packing Dominos in Polynomial Time
Anders Aamand, Mikkel Abrahamsen, Thomas D. Ahle +1
A polyomino is a polygonal region with axis parallel edges and corners of integral coordinates, which may have holes. In this paper, we consider planar tiling and packing problems…