﻿ Polynomials - Microsoft Research
Understanding Polynomials

A catalog of the types of shapes generated by polynomials of various orders in one, two and three dimensions.

Computer graphicists model shapes with polynomials. Simple linear polynomials generate flat polygons; higher order polynomials generate curved lines and surfaces. In order to develop algorithms for modeling and rendering such shapes we must have an intimate understanding of how the coefficients of the polynomials relate to the geometric shapes they generate. The answers to various geometric questions are expressed in terms of new polynomials built out of the coefficients of the original polynomial. The problem is that, for fairly simple shapes, these new polynomials can get incredibly complicated. For example, the condition that a cubic curve has a double point results in a test expression that is a 12th order polynomial in the cubic’s coefficients, and this test expression has over 10000 terms! Fortunately there is a better way to deal with this problem. The research we are doing here builds on a graphical notation technique that was originally proposed by Sylvester and Clifford over 100 years ago. We are now translating many of the results of classical invariant theory into this notation. This has led to a much better visualization of the relation between a polynomial’s shape and its coefficients and has produced new algorithms for solving and factoring polynomials. Our ultimate goal is a new catalog of all the interesting algebraic relations between polynomial coefficients and their shape, describing curves and surfaces of orders up to 4 or 5 in a way that their processing can be accurately computed by parallel processors such as modern GPU’s.

Publications