Mikkel Abrahamsen

SODA Conference 2025 Conference Paper

Partitioning a Polygon Into Small Pieces

• Mikkel Abrahamsen
• Nichlas Langhoff Rasmussen

FOCS Conference 2024 Conference Paper

Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares

• Mikkel Abrahamsen
• Jack Stade

We show that packing axis-aligned unit squares into a simple polygon $P$ is NP-hard, even when $P$ is an orthogonal and orthogonally convex polygon with half-integer coordinates. It has been known since the early 80s that packing unit squares into a polygon with holes is NP-hard [Fowler, Paterson, Tanimoto, Inf. Process. Lett. , 1981], but the version without holes was conjectured to be polynomial-time solvable more than two decades ago [Baur and Fekete, Algorithmica, 2001]. Our reduction relies on a new way of reducing from Planar-3sat. Interestingly, our geometric realization of a planar formula is non-planar. Vertices become rows and edges become columns, with crossings being allowed. The planarity ensures that all endpoints of rows and columns are incident to the outer face of the resulting drawing. We can then construct a polygon following the outer face that realizes all the logic of the formula geometrically, without the need of any holes. This new reduction technique proves to be general enough to also show hardness of two natural covering and partitioning problems, even when the input polygon is simple. We say that a polygon $Q$ is small if $Q$ is contained in a unit square. We prove that it is NP-hard to find a minimum number of small polygons whose union is $P$ (covering) and to find a minimum number of pairwise interior-disjoint small polygons whose union is $P$ (partitioning), when $P$ is an orthogonal simple polygon with half-integer coordinates. This is the first partitioning problem known to be NP-hard for polygons without holes, with the usual objective of minimizing the number of pieces.

STOC Conference 2024 Conference Paper

Minimum Star Partitions of Simple Polygons in Polynomial Time

• Mikkel Abrahamsen
• Joakim Blikstad
• André Nusser
• Hanwen Zhang 0003

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].

AAMAS Conference 2023 Conference Paper

Coordination of Multiple Robots along Given Paths with Bounded Junction Complexity

• Mikkel Abrahamsen
• Tzvika Geft
• Dan Halperin
• Barak Ugav

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 path in 𝐺. 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 agent 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 subproblem 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 ≤ 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 𝐺 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.

SODA Conference 2023 Conference Paper

Online Sorting and Translational Packing of Convex Polygons

• Anders Aamand
• Mikkel Abrahamsen
• Lorenzo Beretta 0001
• Linda Kleist

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 space. Among other variants, we consider strip packing and bin packing, where the container is the infinite horizontal strip [0, ∞) × [0, 1] or a collection of 1 × 1 bins, respectively. If polygons may be rotated, there exist O (1)-competitive online algorithms for all problems at hand [Baker and Schwarz, SIAM J. Comput. , 1983]. Likewise, if the polygons may not be rotated but only translated, then using a result from [Alt, de Berg and Knauer, JoCG, 2017] we can derive O (1)-approximation algorithms for all problems at hand. Thus, it is natural to conjecture that the online version of these problems, in which only translations are allowed, also admits a O (1)-competitive algorithm. We disprove this conjecture by showing a superconstant lower bound on the competitive ratio for several online packing problems. The offline approximation algorithm for translation-only packing sorts the convex polygons by their “natural slope”, so that they form a fan-like pattern. We prove that this step is essential, in the sense that packing polygons without rotating them is as hard as sorting numbers online. Technically, we prove lower bounds on the competitive ratio of translation-only online packing problems by reducing from a purpose-built novel and natural combinatorial problem that we call online sorting. In a nutshell, the problem requires us to place n numbers x 1, …, x n coming online into an oversized array of length γ n for γ ≥ 1, while minimizing the sum of absolute differences of consecutive numbers. Note that the offline optimum is achieved by sorting x 1, …, x n. We show a superconstant lower bound on the competitive ratio of online sorting, for any constant γ. We prove that this yields superconstant lower bounds for all packing problems at hand. We believe that this technique is of independent interest since it uncovers a deep connection between inherently geometrical and purely combinatorial problems. As a complement, we also include algorithms for both online sorting and translation-only online strip packing with non-trivial competitive ratios. Our algorithm for strip packing relies on a new technique for recursively subdividing the strip into parallelograms of varying height, thickness and slope.

FOCS Conference 2021 Conference Paper

Covering Polygons is Even Harder

• Mikkel Abrahamsen

In the Minimum Convex Cover (MCC) problem, we are given a simple polygon $\mathcal{P}$ and an integer $k$, and the question is if there exist $k$ convex polygons whose union is $\mathcal{P}$. It is known that MCC is NP-hard [Culberson & Reckhow: Covering polygons is hard, FOCS 1988/Journal of Algorithms 1994] and in $\exists \mathbb{R}$ [O'Rourke: The complexity of computing minimum convex covers for polygons, Allerton 1982]. We prove that MCC is $\exists \mathbb{R}$ -hard, and the problem is thus $\exists \mathbb{R}$ -complete. In other words, the problem is equivalent to deciding whether a system of polynomial equations and inequalities with integer coefficients has a real solution. If a cover for our constructed polygon exists, then so does a cover consisting entirely of triangles. As a byproduct, we therefore also establish that it is $\exists \mathbb{R}$ -complete to decide whether $k$ triangles cover a given polygon. The issue that it was not known if finding a minimum cover is in N P has repeatedly been raised in the literature, and it was mentioned as a “long-standing open question” already in 2001 [Eidenbenz & Widmayer: An approximation algorithm for minimum convex cover with logarithmic performance guarantee, ESA 2001/SIAM Journal on Computing 2003]. We prove that assuming the widespread belief that $\mathsf{NP}\neq\exists \mathbb{R}$, the problem is not in N P. An implication of the result is that many natural approaches to finding small covers are bound to give suboptimal solutions in some cases, since irrational coordinates of arbitrarily high algebraic degree can be needed for the corners of the pieces in an optimal solution.

NeurIPS Conference 2021 Conference Paper

Training Neural Networks is ER-complete

• Mikkel Abrahamsen
• Linda Kleist
• Tillmann Miltzow

Given a neural network, training data, and a threshold, finding weights for the neural network such that the total error is below the threshold is known to be NP-hard. 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 gives an explanation why techniques commonly used to solve big instances of NP-complete problems (such as SAT solvers, IP solvers, local search, dynamic programming, etc. ) seem to be of no use to this task.

FOCS Conference 2020 Conference Paper

Framework for ER-Completeness of Two-Dimensional Packing Problems

• Mikkel Abrahamsen
• Tillmann Miltzow
• Nadja Seiferth

We show that many natural two-dimensional packing problems are algorithmically equivalent to finding real roots of multivariate polynomials. A two-dimensional packing problem is defined by the type of pieces, containers, and motions that are allowed. The aim is to decide if a given set of pieces can be placed inside a given container. The pieces must be placed so that in the resulting placement, they are pairwise interior-disjoint, and only motions of the allowed type can be used to move them there. We establish a framework which enables us to show that for many combinations of allowed pieces, containers, and motions, the resulting problem is ER-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. A full version of this extended abstract is available on https: //arxiv. org/abs/1704. 06969.

STOC Conference 2018 Conference Paper

Fast fencing

• Mikkel Abrahamsen
• Anna Adamaszek
• Karl Bringmann
• Vincent Cohen-Addad
• Mehran Mehr
• Eva Rotenberg
• Alan Roytman
• Mikkel Thorup

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 S of n points in the plane, we aim at finding a set of closed curves such that (1) each point is enclosed by a curve and (2) the total length of the curves is minimized. We consider two main variants. In the first variant, we pay a unit cost per curve in addition to the total length of the curves. An equivalent formulation of this version is that we have to enclose n unit disks, paying only the total length of the enclosing curves. In the other variant, we are allowed to use at most k closed curves and pay no cost per curve. For the variant with at most k closed curves,we present an algorithm that is polynomialin both n and k . For the variant with unit cost per curve, or unit disks, we presenta near-linear time algorithm. Capoyleas, Rote, and Woeginger solved the problem with at most k curves in n O ( k ) time. Arkin, Khuller, and Mitchell used this to solve the unit cost per curve version in exponential time. At the time, they conjectured that the problem with k curves is NP-hard for general k . Our polynomial time algorithm refutes this unless P equals NP.

STOC Conference 2018 Conference Paper

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 art gallery problem is a classic problem in computational geometry, introduced in 1973 by Victor Klee. Given a simple polygon P and an integer k , the goal is to decide if there exists a set G of k guards within P such that every point p ∈ P is seen by at least one guard g ∈ G . Each guard corresponds to a point in the polygon P , and we say that a guard g sees a point p if the line segment pg is contained in P . The art gallery problem has stimulated extensive research in geometry and in algorithms. However, the complexity status of the art gallery problem has not been resolved. It has long been known that the problem is NP-hard, but no one has been able to show that it lies in NP. Recently, the computational geometry community became more aware of the complexity class ∃ ℝ, which has been studied earlier by other communities. The class ∃ ℝ consists of problems that can be reduced in polynomial time to the problem of deciding whether a system of polynomial equations with integer coefficients and any number of real variables has a solution. It can be easily seen that NP ⊆ ∃ ℝ. We prove that the art gallery problem is ∃ ℝ-complete, implying that (1) any system of polynomial equations over the real numbers can be encoded as an instance of the art gallery problem, and (2) the art gallery problem is not in the complexity class NP unless NP =∃ ℝ. As an illustration of our techniques, we can show that for every compact semi-algebraic set S ⊂ [0,1] 2 there exists a polygon with rational coordinates that enforces one of the guards to be at any position p ∈ S , in any optimal guarding. As a corollary of our construction, we prove that for any real algebraic number α there is an instance of the art gallery problem where one of the coordinates of the guards equals α in any guard set of minimum cardinality. That rules out many natural geometric approaches to the problem, as it shows that any approach based on constructing a finite set of candidate points for placing guards has to include points with coordinates being roots of polynomials with arbitrary degree. In the ∃ ℝ-hardness proof for the art gallery problem we introduce a new ∃ ℝ-complete problem ETR-INV. We believe that this problem is of independent interest, as it can be used to obtain ∃ ℝ-hardness proofs for other problems. In particular, ETR-INV has been very recently used to prove ∃ ℝ-hardness of other geometric problems.