This paper describes an algorithm for generating a guaranteed intersection-free interpolation sequence between any pair of compatible polygons. Our algorithm builds on prior results from linkage unfolding, and if desired it can ensure that every edge length changes monotonically over the course of the interpolation sequence. The computational machinery that ensures against self-intersection is independent from a distance metric that determines the overall character of the interpolation sequence. This decoupled approach provides a powerful control mechanism for determining how the interpolation should appear, while still assuring against intersection and guaranteeing termination of the algorithm. Our algorithm also allows additional control by accommodating a set of algebraic constraints that can be weakly enforced throughout the interpolation sequence.

We present a new algorithm for unfolding planar polygonal link-ages without self-intersection based on following the gradient flow of a "repulsive" energy function. This algorithm has several advantages over previous methods. (1) The output motion is represented explicitly and exactly as a piecewise-linear curve in angle space. As a consequence, an exact snapshot of the linkage at any time can be extracted from the output in strongly polynomial time (on a real RAM supporting arithmetic, radicals, and trigonometric functions). (2) Each linear step of the motion can be computed exactly in O(n2) time on a real RAM where n is the number of vertices. (3) We explicitly bound the number of linear steps (and hence the running time) as a polynomial in n and the ratio between the maximum edge length and the initial minimum distance between a vertex and an edge. (4) Our method is practical and easy to implement. We provide a publicly accessible Java applet that implements the algorithm.

A planar shape S is a k-fold tile if there is an indexed family T of planar shapes congruent to S that is a k-fold tiling: any point in R2 that is not on the boundary of any shape in T is covered by exactly k shapes in T. Since a 1-fold tile is clearly a k-fold tile for any positive integer k, the subjects of our research are nontrivial k-fold tiles, that is, plane shapes with property “not a 1-fold tile, but a k(≥ 2)-fold tile.” In this paper, we prove some interesting properties about nontrivial k-fold tiles. First, we show that, for any integer k ≥ 2, there exists a polyomino with property “not an h-fold tile for any positive integer h < k, but a k-fold tile.” We also find, for any integer k ≥ 2, polyominoes with the minimum number of cells among ones that are nontrivial k-fold tiles. Next, we prove that, for any integer k = 5 or k ≥ 7, there exists a convex unit-lattice polygon that is a nontrivial k-fold tile whose area is k, and for k = 2 and k = 3, no such convex unit-lattice polygon exists.