A FEASIBLE ALGORITHM FOR CHECKING n-SCISSORS CONGRUENCE OF POLYHEDRA IN R~d

摘要

While in R2, every two polygons of the same area are scissors congruent (i.e., they can be both decomposed into the same finite number of pair-wise congruent polygonal pieces), in R3, there are polyhedra P and P' of the same volume which are not scissors-congruent. It is therefore necessary, given two polyhedra, to check whether they are scissors-congruent (and if yes - to find the corresponding decompositions). It is known that while there are algorithms for performing this checking-and-finding task, no such algorithm can be feasible - their worst-case computation time grows (at least) exponentially, so even for reasonable size inputs, the computation time exceeds the lifetime of the Universe. It is therefore desirable to find cases when feasible algorithms are possible. In this paper, we show that for each dimension d, a feasible algorithm is possible if we fix some integer n and look for n-scissors-congruence in R~d - i.e., for possibility to represent P and P' as a union of ≤ n simplexes.