MAMikkel Abrahamsen
Mikkel Abrahamsen
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Mikkel Abrahamsen has a total of 30 co-authors. Here are the top co-authors by number of shared publications:
- Tillmann Miltzow
Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands
5 shared publications - Linda Kleist
Universität Potsdam
3 shared publications - Ali D. Mehrabi
Department of Computer Science TU Eindhoven the Netherlands
2 shared publications Anders Aamand
Basic Algorithms Research Copenhagen (BARC), University of Copenhagen, Copenhagen, Denmark
2 shared publications- André Nusser
Université Côte d' Azur CNRS Inria Sophia Antipolis France
2 shared publications - Günter Rote
Institut für Informatik, Freie Universität Berlin
2 shared publications
Latest Publications
- Open Access
- 13 January 2026
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 5
Minimum Star Partitions of Simple Polygons in Polynomial Time
We devise a polynomial-time algorithm for partitioning a simple polygon $P$ into a minimum number of star-shaped polygons. The question of whether such an algorithm exists has been open for more than four decades [Avis and Toussaint, Pattern Recognit., 1981] and it has been repeated frequently, for example in O'Rourke's famous book [Art Gallery Theorems and Algorithms, 1987]. In addition to its strong theoretical motivation, the problem is also motivated by practical domains such as CNC pocket milling, motion planning, and shape parameterization. The only previously known algorithm for a non-trivial special case is for $P$ being both monotone and rectilinear [Liu and Ntafos, Algorithmica, 1991]. For general polygons, an algorithm was only known for the restricted version in which Steiner points are disallowed [Keil, SIAM J. Comput., 1985], meaning that each corner of a piece in the partition must also be a corner of $P$. Interestingly, the solution size for the restricted version may be linear for instances where the unrestricted solution has constant size. The covering variant in which the pieces are star-shaped but allowed to overlap--known as the Art Gallery Problem--was recently shown to be $\exists\mathbb R$-complete and is thus likely not in NP [Abrahamsen, Adamaszek and Miltzow, STOC 2018 & J. ACM 2022]; this is in stark contrast to our result. Arguably the most related work to ours is the polynomial-time algorithm to partition a simple polygon into a minimum number of convex pieces by Chazelle and Dobkin [STOC, 1979 & Comp. Geom., 1985]. 68 pages. This is the TheoretiCS journal version- 13 January 2026
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 5
Open AccessMinimum Star Partitions of Simple Polygons in Polynomial Time
We devise a polynomial-time algorithm for partitioning a simple polygon $P$ into a minimum number of star-shaped polygons. The question of whether such an algorithm exists has been open for more than four decades [Avis and Toussaint, Pattern Recognit., 1981] and it has been repeated frequently, for example in O'Rourke's famous book [Art Gallery Theorems and Algorithms, 1987]. In addition to its strong theoretical motivation, the problem is also motivated by practical domains such as CNC pocket milling, motion planning, and shape parameterization. The only previously known algorithm for a non-trivial special case is for $P$ being both monotone and rectilinear [Liu and Ntafos, Algorithmica, 1991]. For general polygons, an algorithm was only known for the restricted version in which Steiner points are disallowed [Keil, SIAM J. Comput., 1985], meaning that each corner of a piece in the partition must also be a corner of $P$. Interestingly, the solution size for the restricted version may be linear for instances where the unrestricted solution has constant size. The covering variant in which the pieces are star-shaped but allowed to overlap--known as the Art Gallery Problem--was recently shown to be $\exists\mathbb R$-complete and is thus likely not in NP [Abrahamsen, Adamaszek and Miltzow, STOC 2018 & J. ACM 2022]; this is in stark contrast to our result. Arguably the most related work to ours is the polynomial-time algorithm to partition a simple polygon into a minimum number of convex pieces by Chazelle and Dobkin [STOC, 1979 & Comp. Geom., 1985]. 68 pages. This is the TheoretiCS journal version - Open Access
- 24 January 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (1) , 1-26
Geometric Embeddability of Complexes is ∃ℝ-complete
We show that the decision problem of determining whether a given (abstract simplicial) k -complex has a geometric embedding in ℝ d is complete for the Existential Theory of the Reals for all d ≥ 3 and k ∈ { d -1, d } by reducing from pseudoline stretchability. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometrically embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability [Matoušek, Sedgwick, Tancer, and Wagner, J. ACM 2018, and de Mesmay, Rieck, Sedgwick and Tancer, J. ACM 2020] and establishes connections to computational topology.
- 24 January 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (1) , 1-26
Open AccessGeometric Embeddability of Complexes is ∃ℝ-complete
We show that the decision problem of determining whether a given (abstract simplicial) k -complex has a geometric embedding in ℝ d is complete for the Existential Theory of the Reals for all d ≥ 3 and k ∈ { d -1, d } by reducing from pseudoline stretchability. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometrically embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability [Matoušek, Sedgwick, Tancer, and Wagner, J. ACM 2018, and de Mesmay, Rieck, Sedgwick and Tancer, J. ACM 2020] and establishes connections to computational topology.
- Open Access
ExpoSort: Breaking the quasi-polynomial-time barrier for reluctant sorting
We introduce the algorithm ExpoSort, a groundbreaking method that sorts an array of $n$ numbers in a spectacularly inefficient $Θ(2^n)$ time. ExpoSort proudly claims the title of the first reluctant algorithm to decisively surpass the quasi-polynomial running time $Ω(n^{\log n/(2+\varepsilon)})$ of the notoriously sluggish SlowSort algorithm by Broder and Stolfi [ACM SIGACT News, 1984]. In the ongoing quest for the slowest possible sort, ExpoSort redefines what it means to take one's time. Remarkably, ExpoSort achieves this feat with one of the simplest pseudocodes among all known sorting algorithms. However, a slight modification -- merely moving one recursive call inside an if statement -- transforms ExpoSort into an astonishingly well-camouflaged variant of the classic InsertionSort with best- and worst-case running times of $Θ(n)$ and $Θ(n^3)$, respectively. This dual nature of ExpoSort serves as a reminder of the utmost care required when crafting pessimal algorithms, where a slight lapse in judgment could result in accidentally producing an embarrassingly practical algorithm.Open AccessExpoSort: Breaking the quasi-polynomial-time barrier for reluctant sorting
We introduce the algorithm ExpoSort, a groundbreaking method that sorts an array of $n$ numbers in a spectacularly inefficient $Θ(2^n)$ time. ExpoSort proudly claims the title of the first reluctant algorithm to decisively surpass the quasi-polynomial running time $Ω(n^{\log n/(2+\varepsilon)})$ of the notoriously sluggish SlowSort algorithm by Broder and Stolfi [ACM SIGACT News, 1984]. In the ongoing quest for the slowest possible sort, ExpoSort redefines what it means to take one's time. Remarkably, ExpoSort achieves this feat with one of the simplest pseudocodes among all known sorting algorithms. However, a slight modification -- merely moving one recursive call inside an if statement -- transforms ExpoSort into an astonishingly well-camouflaged variant of the classic InsertionSort with best- and worst-case running times of $Θ(n)$ and $Θ(n^3)$, respectively. This dual nature of ExpoSort serves as a reminder of the utmost care required when crafting pessimal algorithms, where a slight lapse in judgment could result in accidentally producing an embarrassingly practical algorithm. - Open Access
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 904-910
Minimum Star Partitions of Simple Polygons in Polynomial Time
We devise a polynomial-time algorithm for partitioning a simple polygon P into a minimum number of star-shaped polygons. The question of whether such an algorithm exists has been open for more than four decades [Avis and Toussaint, Pattern Recognit., 1981] and it has been repeated frequently, for example in O’Rourke’s famous book [Art Gallery Theorems and Algorithms, 1987]. In addition to its strong theoretical motivation, the problem is also motivated by practical domains such as CNC pocket milling, motion planning, and shape parameterization. The only previously known algorithm for a non-trivial special case is for P being both monotone and rectilinear [Liu and Ntafos, Algorithmica, 1991]. For general polygons, an algorithm was only known for the restricted version in which Steiner points are disallowed [Keil, SIAM J. Comput., 1985], meaning that each corner of a piece in the partition must also be a corner of P. Interestingly, the solution size for the restricted version may be linear for instances where the unrestricted solution has constant size. The covering variant in which the pieces are star-shaped but allowed to overlap—known as the Art Gallery Problem—was recently shown to be ∃ℝ-complete and is thus likely not in NP [Abrahamsen, Adamaszek and Miltzow, STOC 2018 & J. ACM 2022]; this is in stark contrast to our result. Arguably the most related work to ours is the polynomial-time algorithm to partition a simple polygon into a minimum number of convex pieces by Chazelle and Dobkin [STOC, 1979 & Comp. Geom., 1985].
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 904-910
Open AccessMinimum Star Partitions of Simple Polygons in Polynomial Time
We devise a polynomial-time algorithm for partitioning a simple polygon P into a minimum number of star-shaped polygons. The question of whether such an algorithm exists has been open for more than four decades [Avis and Toussaint, Pattern Recognit., 1981] and it has been repeated frequently, for example in O’Rourke’s famous book [Art Gallery Theorems and Algorithms, 1987]. In addition to its strong theoretical motivation, the problem is also motivated by practical domains such as CNC pocket milling, motion planning, and shape parameterization. The only previously known algorithm for a non-trivial special case is for P being both monotone and rectilinear [Liu and Ntafos, Algorithmica, 1991]. For general polygons, an algorithm was only known for the restricted version in which Steiner points are disallowed [Keil, SIAM J. Comput., 1985], meaning that each corner of a piece in the partition must also be a corner of P. Interestingly, the solution size for the restricted version may be linear for instances where the unrestricted solution has constant size. The covering variant in which the pieces are star-shaped but allowed to overlap—known as the Art Gallery Problem—was recently shown to be ∃ℝ-complete and is thus likely not in NP [Abrahamsen, Adamaszek and Miltzow, STOC 2018 & J. ACM 2022]; this is in stark contrast to our result. Arguably the most related work to ours is the polynomial-time algorithm to partition a simple polygon into a minimum number of convex pieces by Chazelle and Dobkin [STOC, 1979 & Comp. Geom., 1985].
- Open Access
- 14 July 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 19 (3) , 1-28
Tiling with Squares and Packing Dominos in Polynomial Time
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 with polyomino pieces and a polyomino container P . We give polynomial-time algorithms for deciding if P can be tiled with k × k squares for any fixed k which can be part of the input (that is, deciding if P is the union of a set of non-overlapping k × k squares) and for packing P with a maximum number of non-overlapping and axis-parallel 2 × 1 dominos, allowing rotations by 90°. As packing is more general than tiling, the latter algorithm can also be used to decide if P can be tiled by 2 × 1 dominos. These are classical problems with important applications in VLSI design, and the related problem of finding a maximum packing of 2 × 2 squares is known to be NP-hard [ 6 ]. For our three problems there are known pseudo-polynomial-time algorithms, that is, algorithms with running times polynomial in the area or perimeter of P . However, the standard, compact way to represent a polygon is by listing the coordinates of the corners in binary. We use this representation, and thus present the first polynomial-time algorithms for the problems. Concretely, we give a simple O(n log n )-time algorithm for tiling with squares, where n is the number of corners of P . We then give a more involved algorithm that reduces the problems of packing and tiling with dominos to finding a maximum and perfect matching in a graph with O ( n 3 ) vertices. This leads to algorithms with running times \(O(n^3 \frac{\log ^3 n}{\log ^2\log n})\) and \(O(n^3 \frac{\log ^2 n}{\log \log n})\) , respectively.- 14 July 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 19 (3) , 1-28
Open AccessTiling with Squares and Packing Dominos in Polynomial Time
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 with polyomino pieces and a polyomino container P . We give polynomial-time algorithms for deciding if P can be tiled with k × k squares for any fixed k which can be part of the input (that is, deciding if P is the union of a set of non-overlapping k × k squares) and for packing P with a maximum number of non-overlapping and axis-parallel 2 × 1 dominos, allowing rotations by 90°. As packing is more general than tiling, the latter algorithm can also be used to decide if P can be tiled by 2 × 1 dominos. These are classical problems with important applications in VLSI design, and the related problem of finding a maximum packing of 2 × 2 squares is known to be NP-hard [ 6 ]. For our three problems there are known pseudo-polynomial-time algorithms, that is, algorithms with running times polynomial in the area or perimeter of P . However, the standard, compact way to represent a polygon is by listing the coordinates of the corners in binary. We use this representation, and thus present the first polynomial-time algorithms for the problems. Concretely, we give a simple O(n log n )-time algorithm for tiling with squares, where n is the number of corners of P . We then give a more involved algorithm that reduces the problems of packing and tiling with dominos to finding a maximum and perfect matching in a graph with O ( n 3 ) vertices. This leads to algorithms with running times \(O(n^3 \frac{\log ^3 n}{\log ^2\log n})\) and \(O(n^3 \frac{\log ^2 n}{\log \log n})\) , respectively. - Open Access
Coordination of Multiple Robots along Given Paths with Bounded Junction Complexity
We study a fundamental NP-hard motion coordination problem for multi-robot/multi-agent systems: We are given a graph $G$ and set of agents, where each agent has a given directed path in $G$. Each agent is initially located on the first vertex of its path. At each time step an agent can move to the next vertex on its path, provided that the vertex is not occupied by another agent. The goal is to find a sequence of such moves along the given paths so that each reaches its target, or to report that no such sequence exists. The problem models guidepath-based transport systems, which is a pertinent abstraction for traffic in a variety of contemporary applications, ranging from train networks or Automated Guided Vehicles (AGVs) in factories, through computer game animations, to qubit transport in quantum computing. It also arises as a sub-problem in the more general multi-robot motion-planning problem. We provide a fine-grained tractability analysis of the problem by considering new assumptions and identifying minimal values of key parameters for which the problem remains NP-hard. Our analysis identifies a critical parameter called vertex multiplicity (VM), defined as the maximum number of paths passing through the same vertex. We show that a prevalent variant of the problem, which is equivalent to Sequential Resource Allocation (concerning deadlock prevention for concurrent processes), is NP-hard even when VM is 3. On the positive side, for VM $\le$ 2 we give an efficient algorithm that iteratively resolves cycles of blocking relations among agents. We also present a variant that is NP-hard when the VM is 2 even when $G$ is a 2D grid and each path lies in a single grid row or column. By studying highly distilled yet NP-hard variants, we deepen the understanding of what makes the problem intractable and thereby guide the search for efficient solutions under practical assumptions.Open AccessCoordination of Multiple Robots along Given Paths with Bounded Junction Complexity
We study a fundamental NP-hard motion coordination problem for multi-robot/multi-agent systems: We are given a graph $G$ and set of agents, where each agent has a given directed path in $G$. Each agent is initially located on the first vertex of its path. At each time step an agent can move to the next vertex on its path, provided that the vertex is not occupied by another agent. The goal is to find a sequence of such moves along the given paths so that each reaches its target, or to report that no such sequence exists. The problem models guidepath-based transport systems, which is a pertinent abstraction for traffic in a variety of contemporary applications, ranging from train networks or Automated Guided Vehicles (AGVs) in factories, through computer game animations, to qubit transport in quantum computing. It also arises as a sub-problem in the more general multi-robot motion-planning problem. We provide a fine-grained tractability analysis of the problem by considering new assumptions and identifying minimal values of key parameters for which the problem remains NP-hard. Our analysis identifies a critical parameter called vertex multiplicity (VM), defined as the maximum number of paths passing through the same vertex. We show that a prevalent variant of the problem, which is equivalent to Sequential Resource Allocation (concerning deadlock prevention for concurrent processes), is NP-hard even when VM is 3. On the positive side, for VM $\le$ 2 we give an efficient algorithm that iteratively resolves cycles of blocking relations among agents. We also present a variant that is NP-hard when the VM is 2 even when $G$ is a 2D grid and each path lies in a single grid row or column. By studying highly distilled yet NP-hard variants, we deepen the understanding of what makes the problem intractable and thereby guide the search for efficient solutions under practical assumptions. - 14 July 2022
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 69 (4) , 1195-1231
How to Cut Corners and Get Bounded Convex Curvature
- 14 July 2022
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 69 (4) , 1195-1231
How to Cut Corners and Get Bounded Convex Curvature
- Open Access
Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems
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 handled, and the motions that are allowed to move the pieces. The pieces must be placed so that in the resulting placement, they are pairwise interior-disjoint. We establish a framework which enables us to show that for many combinations of allowed pieces, containers and motions, the resulting problem is $\exists \mathbb{R}$-complete. This means that the problem is equivalent (under polynomial time reductions) to deciding whether a given system of polynomial equations and inequalities with integer coefficients has a real solution. We consider packing problems where only translations are allowed as the motions, and problems where arbitrary rigid motions are allowed, i.e., both translations and rotations. When rotations are allowed, we show that it is an $\exists \mathbb{R}$-complete problem to decide if a set of convex polygons, each of which has at most $7$ corners, can be packed into a square. Restricted to translations, we show that the following problems are $\exists \mathbb{R}$-complete: (i) pieces bounded by segments and hyperbolic curves to be packed in a square, and (ii) convex polygons to be packed in a container bounded by segments and hyperbolic curves.Open AccessFramework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems
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 handled, and the motions that are allowed to move the pieces. The pieces must be placed so that in the resulting placement, they are pairwise interior-disjoint. We establish a framework which enables us to show that for many combinations of allowed pieces, containers and motions, the resulting problem is $\exists \mathbb{R}$-complete. This means that the problem is equivalent (under polynomial time reductions) to deciding whether a given system of polynomial equations and inequalities with integer coefficients has a real solution. We consider packing problems where only translations are allowed as the motions, and problems where arbitrary rigid motions are allowed, i.e., both translations and rotations. When rotations are allowed, we show that it is an $\exists \mathbb{R}$-complete problem to decide if a set of convex polygons, each of which has at most $7$ corners, can be packed into a square. Restricted to translations, we show that the following problems are $\exists \mathbb{R}$-complete: (i) pieces bounded by segments and hyperbolic curves to be packed in a square, and (ii) convex polygons to be packed in a container bounded by segments and hyperbolic curves. - Open Access
Training Neural Networks is $\exists\mathbb R$-complete
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 determine the algorithmic complexity of this fundamental problem precisely, by showing that it is $\exists\mathbb R$-complete. This means that the problem is equivalent, up to polynomial-time reductions, to deciding whether a system of polynomial equations and inequalities with integer coefficients and real unknowns has a solution. If, as widely expected, $\exists\mathbb R$ is strictly larger than NP, our work implies that the problem of training neural networks is not even in NP. Neural networks are usually trained using some variation of backpropagation. The result of this paper offers an explanation why techniques commonly used to solve big instances of NP-complete problems seem not to be of use for this task. Examples of such techniques are SAT solvers, IP solvers, local search, dynamic programming, to name a few general ones.Open AccessTraining Neural Networks is $\exists\mathbb R$-complete
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 determine the algorithmic complexity of this fundamental problem precisely, by showing that it is $\exists\mathbb R$-complete. This means that the problem is equivalent, up to polynomial-time reductions, to deciding whether a system of polynomial equations and inequalities with integer coefficients and real unknowns has a solution. If, as widely expected, $\exists\mathbb R$ is strictly larger than NP, our work implies that the problem of training neural networks is not even in NP. Neural networks are usually trained using some variation of backpropagation. The result of this paper offers an explanation why techniques commonly used to solve big instances of NP-complete problems seem not to be of use for this task. Examples of such techniques are SAT solvers, IP solvers, local search, dynamic programming, to name a few general ones. - Open Access
Geometric Embeddability of Complexes is $\exists \mathbb R$-complete
We show that the decision problem of determining whether a given (abstract simplicial) $k$-complex has a geometric embedding in $\mathbb R^d$ is complete for the Existential Theory of the Reals for all $d\geq 3$ and $k\in\{d-1,d\}$. This implies that the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution. Moreover, this implies NP-hardness and constitutes the first hardness results for the algorithmic problem of geometric embedding (abstract simplicial) complexes.Open AccessGeometric Embeddability of Complexes is $\exists \mathbb R$-complete
We show that the decision problem of determining whether a given (abstract simplicial) $k$-complex has a geometric embedding in $\mathbb R^d$ is complete for the Existential Theory of the Reals for all $d\geq 3$ and $k\in\{d-1,d\}$. This implies that the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution. Moreover, this implies NP-hardness and constitutes the first hardness results for the algorithmic problem of geometric embedding (abstract simplicial) complexes.