Complexity of planar scissor congruence Two (not necessarily convex) poygons of equal area are scissor-congruent, i.e. both can be cut along a finite number of straight lines or segments into isometric pieces.
What can be said about the complexity of scissor congruence?
Remarks: The number of cuts cannot be bounded in terms of the number of sides:
A very thin triangle (of huge diameter) has to be cut into a large number of pieces if the other triangle has small diameter (e.g. is equilateral).
However, the proof of scissor congruence shows that the number of cuts can be bounded if both polygons of area $1$ have bounded diameter $\leq A$ and a bounded number of sides $\leq N$.
Is such a bound a linear function of $A$ and $N$? (The bound can only be slightly worse than linear, I believe.) What are the asymptotics of the
optimal bound?
(The question is still somewhat unprecise since there are several possibilities for counting the number of necessary cuts: one might allow cuts along segments or only along lines, two intersecting cuts can be counted as $2$ or
$3$ cuts, etc.)
Remark: One way to make the question precise, is to ask for the minimal number of pieces (this should not differ to much from the number of necessary cuts in generic situations).
 A: Let's assume you have a good linear bound $O(A)$ when both polygons are triangles of the same area.  I am pretty sure you are right and the standard proof gives this.  More precisely, a sequence triangle $\to$ parallelogram $\to$ square depends only on the smallest angle in a triangle, and thus on $A$. 
Now use the following standard trick (see e.g. my book, $\S$15-18).  For general polygons $(m+2)$ and $(n+2)$ sides, triangulate them into triangles $T_1,\ldots,T_m$, $S_1,\ldots,S_n$.  Denote by $\alpha_i=$area$(T_i)$, $\beta_j=$area$(S_j)$. Triangulate each $T_i$ into $(n+2)$ triangles $T_{ij}$ of areas $\alpha_i\beta_j$, and each $S_j$ into $(m+2)$ triangles $S_{ij}$ of areas $\alpha_i\beta_j$.  Use scissor congruence for $T_{ij}$ and $S_{ij}$.  This gives $O(N^2A)$ bound.  
You can actually improve this to a linear $O(NA)$ bound you want as follows.  Think of an interval of length 1 with points at $\alpha_1,\alpha_1+\alpha_2,\alpha_1+\alpha_2+\alpha_3$, etc.  Do the same for $\beta_i$.  Take a union of these sets of points.  They represent how each $T_i$ and $S_j$ should be cut into triangles.  I trust you see how to finish this.  
