<p>For disconnected one-dimensional regions with integer coordinates, equidecomposition into a minimum number of pieces is strongly NP-hard via an easy reduction to 3SUM: if one shape has segments whose lengths are the 3SUM inputs and the other has segments whose lengths are the bins you have to pack them in, then you can do it with no additional cutting iff the 3SUM instance is solvable. For two-dimensional polygons it remains hard, even for connected regions: thicken the segments of a one-dimensional problem to unit-height rectangles and connect them by thin "strings" that have too small an area to affect the 3SUM part of the problem but are easy to handle in the decomposition.</p>

<p>(Disclaimer: I borrowed this reduction idea from some not-yet-published joint work with many other people on hardness of some other problems.)</p>

CC BY-SA 3.0
2014-07-02T08:08:38.123Z
Your disclaimer seems to be actually an acknowledgment! :-)
David Richerby
CC BY-SA 3.0
2014-07-02T06:10:39.717Z
2014-07-02T06:10:39.717Z
David Eppstein
<p>Given two polyhedra $P$ and $Q$, $P$ and $Q$ are are equidecomposable if there are finite sets of polyhedra $P_1, \ldots, P_n$ and $Q_1, \ldots, Q_n$ such that $P_i$ and $Q_i$ are congruent for all $i$, $P = \cup_{i=1}^n P_i$ and $Q = \cup_{i=1}^n Q_i$. <a href="https://en.wikipedia.org/wiki/Equidecomposable">It is known</a> that if $P$ and $Q$ are polygons of equal area, such an <em>equidecomposition</em> always exists and that this <a href="https://en.wikipedia.org/wiki/Hilbert%27s_third_problem">does not hold in general for higher dimensions</a>.  </p>

<p>I am curious as to the complexity of the minimum equidecomposition problem:</p>

<blockquote>
  <p>For two polygons $P$ and $Q$, find a equidecomposition $P_1, \ldots, P_n$ and $Q_1, \ldots, Q_n$ that minimizes $n$.</p>
</blockquote>

<p>Are there algorithms (exact, polynomial, exponential, approximation) for this?  Is the complexity known?</p>

CC BY-SA 3.0
2014-07-02T01:38:38.057Z
welcome, great [blog](http://blogs.oregonstate.edu/glencora/)!
vzn
<ds.algorithms><computational-geometry><polygon>
Minimum equidecomposable decomposition
Glencora Borradaile
# Minimum equidecomposable decomposition

(Asked by: username_0 on 2014-07-01)

Given two polyhedra $P$ and $Q$, $P$ and $Q$ are are equidecomposable if there are finite sets of polyhedra $P\_1, \ldots, P\_n$ and $Q\_1, \ldots, Q\_n$ such that $P\_i$ and $Q\_i$ are congruent for all $i$, $P = \cup\_{i=1}^n P\_i$ and $Q = \cup\_{i=1}^n Q\_i$. [It is known](https://en.wikipedia.org/wiki/Equidecomposable) that if $P$ and $Q$ are polygons of equal area, such an *equidecomposition* always exists and that this [does not hold in general for higher dimensions](https://en.wikipedia.org/wiki/Hilbert%27s_third_problem).

I am curious as to the complexity of the minimum equidecomposition problem:

> For two polygons $P$ and $Q$, find a equidecomposition $P\_1, \ldots, P\_n$ and $Q\_1, \ldots, Q\_n$ that minimizes $n$.

Are there algorithms (exact, polynomial, exponential, approximation) for this? Is the complexity known?

**Tags:** ds.algorithms, computational-geometry, polygon

> **Comments:**
> **username_1**: welcome, great [blog](http://blogs.oregonstate.edu/glencora/)!  

---

## 1 answers

### Answer by username_2 on 2014-07-02. Score: 6

For disconnected one-dimensional regions with integer coordinates, equidecomposition into a minimum number of pieces is strongly NP-hard via an easy reduction to 3SUM: if one shape has segments whose lengths are the 3SUM inputs and the other has segments whose lengths are the bins you have to pack them in, then you can do it with no additional cutting iff the 3SUM instance is solvable. For two-dimensional polygons it remains hard, even for connected regions: thicken the segments of a one-dimensional problem to unit-height rectangles and connect them by thin "strings" that have too small an area to affect the 3SUM part of the problem but are easy to handle in the decomposition.

(Disclaimer: I borrowed this reduction idea from some not-yet-published joint work with many other people on hardness of some other problems.)

> **Comments:**
> **username_3**: Your disclaimer seems to be actually an acknowledgment! :-)  

---

