Generalizations of Kempe's universality theorem

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.Copyright statement on t.p. reads: ©Timothy Good Abbott, 2004-2007, ©Reid W. Barton, 2004-2007.Includes bibliographical references (p. 85-86).In 1876, A. B. Kempe presented a flawed proof of what is now called Kempe's Universality Theorem: that the intersection of a closed disk with any curve in R2 defined by a polynomial equation can be drawn by a linkage. Kapovich and Millson published the first correct proof of this claim in 2002, but their argument relied on different, more complex constructions. We provide a corrected version of Kempe's proof, using a novel contraparallelogram bracing. The resulting historical proof of Kempe's Universality Theorem uses simpler gadgets than those of Kapovich and Millson. We use our two-dimensional proof of Kempe's theorem to give simple proofs of two extensions of Kempe's theorem first shown by King: a generalization to d dimensions and a characterization of the drawable subsets of Rd. Our results improve King's by proving better continuity properties for the constructions. We prove that our construction requires only O(nd) bars to draw a curve defined by a polynomial of degree n in d dimensions, improving the previously known bounds of O(n4) in two dimensions and O(n6) in three dimensions. We also prove a matching Q(nd) lower bound in the worst case. We give an algorithm for computing a configuration above a given point on a given polynomial curve, running in time polynomial in the size of the dense representation of the polynomial defining the curve. We use this algorithm to prove the coNP-hardness of testing the rigidity of a given configuration of a linkage. While this theorem has long been assumed in rigidity theory, we believe this to be the first published proof that this problem is computationally intractable. This thesis is joint work with Reid W. Barton and Erik D. Demaine.by Timothy Good Abbott.S.M