onvexifying

olygons

 

 

 

 

 

 

 

 

 

 


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

1Johnson, L. W. and R. D. Riess. 1977. Numerical Analysis. Addison-Wesley Publishing Company, 112-158. (notes)

2Cox D., J. Little and D. O'Shea. 1992. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Cummutative Algebra. Springer-Verlag, 1-111. (notes)

Please enable Java for an interactive construction (with Cinderella).