onvexifying

Eleanor Farrington
The
Carpenter's Rule Problem
asks whether it is possible to continuously move a simple, planar polygon
into a position where all of its vertices are convex, without changing the
lengths of the edges, or having edges cross. This problem leads directly
to the determination of the motion of robot arms, which must move continuously
without crossing themselves, while maintaining the same arm lengths. The
problem has been answered positively, leaving the challenge of efficiently
programming and animating this motion.
The first step we took towards programming this motion in Mathematica was creating a system of equations describing the relations between vertices, based on the locations of edges, and then parametrizing this system with respect to a single variable, t. This allowed us to solve for the locations of each vertex based on the location of the moving vertex, the parametrization of which was t itself. There were two options for how to solve the system for each particular t, Newton's Method and Gröbner Bases. Newton's Method uses linear approximations of a function based on the first derivative to find closer and closer guesses for the solution.^{1} A Gröbner Basis is a finite subset of polynomials with a lot of nice properties that describes another set of polynomials.^{2} The relative efficiency of these two methods for solving the systems of polynomial equations was tested using examples created in Cinderella, or randomly generated by a program written in Mathematica. The first Mathematica function we tried using was Solve, which deals with systems of polynomial equations by first finding a Gröbner Basis, because the properties of a Gröbner Basis make it a lot easier for the computer to solve than the original system of equations. Solve was very accurate but tended to be rather slow. Using the Mathematica function GroebnerBasis to first find a Gröbner Basis and then inputting the results of this into Solve tended to be more efficient. Unfortunately, there were some examples that made both Solve and GroebnerBasis crash Mathematica. The other function we tried was FindRoot, which uses Newton's Method. This function tended to work a lot quicker, but had a few problems. If FindRoot could not find an accurate enough answer within a few steps it stops and outputs whatever numbers it last tried, which tended to be very far off. The second major problem with FindRoot was in finding complex solutions. FindRoot can either find all complex solutions or no complex solutions, which caused problems, since the function we wrote was set up to stop when it reached complex solutions. So none of the Mathematica functions appear to be both efficient and accurate, though corresponding functions in other mathematics software may be better. The programs written this summer also only allowed one degree of freedom (determined the locations of the vertices based on the motion of only one vertex), so a major future step will be to allow multiple degrees of freedom. (Supported by the Schultz Foundation) Advisor: Ileana Streinu ^{1}Johnson, L. W. and R. D. Riess. 1977. Numerical Analysis. AddisonWesley Publishing Company, 112158. (notes) ^{2}Cox D., J. Little and D. O'Shea. 1992. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Cummutative Algebra. SpringerVerlag, 1111. (notes) 