# How to make an approximation of path with polynom P(x,y)=0?

Hi. Imagine that a user draws on the canvas any path. I want to approximate this path with a path $P(x,y)=0$ where $P(x,y)$ - is unknown polynom. May be somebody can suggest an appropriate algorithm?

1) I tried to use the method of least squares to find this polynom. Just choosed on the path a lot of points $(x_i,y_i)$ . And minimized unknown $\sum\limits_i P(x_i,y_i)^2$ among all polinoms of degree n. This problem of minimization is a problem of finding an eigen vector of huge matrix that grows as $n^2\times n^2$. Already for $n=7$ this matrix has a size $36\times36$ it's hard work for PC to find the solution. And for $n=7$ it doesn't give appropriate result.

2) Spline doesn't work for me. Because spline - is a union of curves $P_i(x,y)=0$. To each spline of course we can correspond $P(x,y)=\prod\limits_i P_i(x,y)$. But this union $P(x,y)=0$ will have a lot of bifurcation points on the curve. And for my project it is very bad

-
What sort of path is it (e.g. a simple closed loop), of what regularity, and in what sense (in what norm) do you want to approximate it. –  Pietro Majer Jun 5 '12 at 12:48
I want to write following a programm. User draw any path (let say his signature) and programm costruct the mechanical linkage that can draw this path. Because of the "Kempe linkage theorem" I know that it is poossible for any algebraic path P(x,y)=0. –  David Jun 5 '12 at 14:18
About your first solution: the matrix size should not be a problem. I just measured the execution time of Matlab function eig(), which computes eigenvalues: it runs 6 milliseconds for 500 x 500 matrix. Have you implemented the eigenvalue computation by yourself? Which programming language have you used? –  Stanislav Jun 5 '12 at 17:52
Stanislav, because I am writing web application I write everything on Javascript and use JS library "numeric". Thank you for your comment. It seems that it exists much faster algorithms that in my library. Then I'll try to write my own eig() function. –  David Jun 6 '12 at 12:08
@David, given your comments, you are actually interested in a slightly different problem: Given a map $f:[a,b]\to R^2$, approximate $f$ by a polynomial map $p:[a,b]\to R^2$. This should be easier to do than your original problem. Once you find such p, then you can construct a "functional" mechanical linkage L which would "draw" the map p. We explain how to do it in the paper with John Millson "Universality theorems for configuration spaces of planar linkages", which you can find at arxiv.org/abs/math/9803150 –  Misha Jun 8 '12 at 17:22