Abstract
The classic geometric problem of polygon dissection—cutting one polygon into pieces to form another of equal area—has been known to be possible since the 19th century. However, the computational complexity of finding the minimum number of pieces required has remained largely unexplored. This paper proves that finding the minimum number of pieces is NP-hard and even hard to approximate within a constant factor, specifically $1 + 1/1080 - \epsilon$. These results hold for simple orthogonal polygons and are robust across variations in allowed transformations such as rotation and reflection.
Introduction
Since the early 19th century, the Bolyai-Gerwien theorem has guaranteed that any two polygons of equal area can be dissected into one another using a finite number of pieces. While the existence of such a dissection is well-established, the efficiency of the process—minimizing the number of pieces—is poorly understood. For instance, it remains unknown if a square can be transformed into an equilateral triangle using fewer than four pieces.
This paper addresses the computational complexity of the $k$-piece dissection problem: given two polygons $P$ and $Q$ of equal area, is it possible to dissect $P$ into $k$ pieces to form $Q$? The authors provide the first formal proof that both the decision and approximation versions of this problem are computationally intractable.
Methods
The authors employ complexity-theoretic reductions to establish hardness.
NP-Hardness via 5-Partition
The proof for NP-hardness reduces from 5-Partition, a variant of the 3-Partition problem. The authors construct a "source" polygon $P$ containing multiple "element rectangles" representing the numbers to be partitioned, and a "target" polygon $Q$ containing "partition rectangles" (slots).
The geometry is meticulously designed with specific distances ($d_s$ and $d_t$) and thin connecting bars. This setup ensures that the only way to achieve a minimum piece count is to cut the element rectangles cleanly and pack them perfectly into the target slots, thereby solving the underlying 5-Partition instance.
Inapproximability via 4-Dimensional Matching
To prove that even approximating the minimum number of pieces is difficult, the authors reduce from 4-Dimensional Matching (4DM). Using a gap-preserving reduction, they demonstrate that a small difference in the 4DM instance translates into a significant "gap" in the required number of pieces for the dissection.
Key Insights and Ideas
A central technical challenge in these reductions is preventing a single piece from "cheating" by spanning across multiple elements or slots. To solve this, the authors introduced the "Trimmed Rectangle" Lemma.
By using "trimmed" element rectangles (as shown above), the proof forces any valid dissection to treat each element as a distinct unit. Any attempt to use "messy" or diagonal cuts to bridge elements would necessarily increase the total piece count, incentivizing the "clean" cuts that simulate the discrete combinatorial problem.
The proof is remarkably robust, holding for simple orthogonal polygons regardless of whether rotation and reflection are permitted, or whether pieces must remain connected (Jordan regions).
Key Results
The primary contributions of the paper are summarized in two main theorems:
- Theorem 1: The $k$-Piece Dissection problem is NP-hard.
- Theorem 2: The optimization version (Min Piece Dissection) is NP-hard to approximate within a factor of $1 + 1/1080 - \epsilon$.
These results establish that finding the most efficient way to cut and rearrange shapes is fundamentally difficult from a computational perspective.
Limitations and Future Work
Despite these findings, several open questions remain:
- Complexity Class: It is currently unknown if the problem is in NP. Verifying a solution might be difficult if cuts involve complex algebraic curves. The authors suggest the problem might reside in the Existential Theory of the Reals ($\exists\mathbb{R}$).
- Convexity: The current hardness proof utilizes non-convex orthogonal shapes. Whether the problem remains hard when one or both polygons are required to be convex is an open question.
- Fixed $k$: The hardness results apply when $k$ is part of the input. The complexity for a small, fixed $k$ (e.g., $k=5$) remains unknown.
Summary updated