11 citations · 60 across the 20 of their papers we have counts for
7 papers · 1 filter
Online Sorting and Translational Packing of Convex Polygons
Anders Aamand, Mikkel Abrahamsen, Lorenzo Beretta +1
We investigate several online packing problems in which convex polygons arrive one by one and have to be placed irrevocably into a container, while the aim is to minimize the used…
Distinguishing classes of intersection graphs of homothets or similarities of two convex disks
Mikkel Abrahamsen, Bartosz Walczak
For smooth convex disks , i.e., convex compact subsets of the plane with non-empty interior and with at most one tangent at every boundary point, we classify the classes $G^{\te…
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…
Training Neural Networks is -complete
Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow
Given a neural network, training data, and a threshold, it was known that it is NP-hard to find weights for the neural network such that the total error is below the threshold. We…
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…