This is a beautiful paper with two highly original results. First, it is shown that a planar linkage can be forced to stay inside a region by the addition of a polynomial number of new links (polynomial in the number of original links and the number of sides of the region). Second, the reachability question for planar linkages is proved to be PSPACE-hard. This means that for a given initial configuration of an arbitrary linkage, the question of whether it can be moved so that a particular joint in that linkage reaches a predetermined point of the plane is PSPACE-hard.

The essential technique used throughout this paper is to construct complex linkages by putting together simpler special-purpose linkages, some of these simpler linkages date from the late 1800s and give this paper a lot of mathematical charm and elegance. In summary, this is a welcome addition to the recent results in “robotics from a complexity point of view.”