11 citations · 60 across the 20 of their papers we have counts for
28 papers
Coordination of Multiple Robots along Given Paths with Bounded Junction Complexity
Mikkel Abrahamsen, Tzvika Geft, Dan Halperin +1
We study a fundamental NP-hard motion coordination problem for multi-robot/multi-agent systems: We are given a graph and set of agents, where each agent has a given directed pa…
Partitioning a Polygon Into Small Pieces
Mikkel Abrahamsen, Nichlas Langhoff Rasmussen
We study the problem of partitioning a given simple polygon into a minimum number of connected polygonal pieces, each of bounded size. We describe a general technique for const…
Degree of Convexity and Expected Distances in Polygons
Mikkel Abrahamsen, Viktor Fredslund-Hansen
We present an algorithm for computing the so-called Beer-index of a polygon in time, where is the number of corners. The polygon may have holes. The Beer-index…
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…
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…
Framework for -Completeness of Two-Dimensional Packing Problems
Mikkel Abrahamsen, Tillmann Miltzow, Nadja Seiferth
The aim in packing problems is to decide if a given set of pieces can be placed inside a given container. A packing problem is defined by the types of pieces and containers to be h…
Dynamic Toolbox for ETRINV
Mikkel Abrahamsen, Tillmann Miltzow
Recently, various natural algorithmic problems have been shown to be -complete. The reduction relied in many cases on the -completeness of t…
Disks in Curves of Bounded Convex Curvature
Anders Aamand, Mikkel Abrahamsen, Mikkel Thorup
We say that a simple, closed curve in the plane has bounded convex curvature if for every point on , there is an open unit disk and such that $x\…
Geometric Multicut
Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler +1
We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest "fence" , i.e., a union of curves of minimum total length, that…
Classifying Convex Bodies by their Contact and Intersection Graphs
Anders Aamand, Mikkel Abrahamsen, Jakob Bæk Tejs Knudsen +1
Suppose that is a convex body in the plane and that are translates of . Such translates give rise to an intersection graph of , , with vertices $…
Fast Fencing
Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann +5
We consider very natural "fence enclosure" problems studied by Capoyleas, Rote, and Woeginger and Arkin, Khuller, and Mitchell in the early 90s. Given a set of points in th…
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…
Near-Optimal Induced Universal Graphs for Bounded Degree Graphs
Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm +2
A graph is an induced universal graph for a family of graphs if every graph in is a vertex-induced subgraph of . For the family of all undirected graphs on verti…