2

1

Assume we are given the set $S$ of $n$ points on the real plane and want to draw a parametrized cubic curve (actually a segment of Bezier spline) with fixed startpoint in such a way, that the resulting curve is closest to $S$. $S$ may be assumed to contain at least three different points. By closest I mean such a curve, that the sum of distances between it and every point of $S$ is minimal (however I think the sum of squares of distances will be ok either). Drawing a cubic curve with fixed startpoint amounts to specifying 6 coefficients in the parametric presentation and the problem is to find way of expressing these coefficients through the given coordinates of points in $S$. Is there any solution to the problem?

flag
You probably want to work with the sum of squares of distances. Then standard least-squares methods should work. But I haven't actually done the algebra. – Michael Lugo Apr 7 2011 at 15:58
LMC will work, but it minimizes slightly different thing, namely the sum of squares of distances between points of S and some specific knots (each for every point of S) on the curve. For programming purposes this is enough, of course. – isnmr Apr 7 2011 at 16:18
1 
 Honestly, I do not see how the LSM works here because, unlike the distance to the line, the (signed) distance to the curve is not linear in the parameters (actually, it has no nice explicit formula whatsoever). I wonder if there is some convexity in the problem that would ensure at least that the local minimizer is unique. Then the gradient descend method has a chance to work :) – fedja Apr 7 2011 at 17:57
fedja, that's a good point. Like I said, I didn't actually do the algebra. – Michael Lugo Apr 8 2011 at 13:58

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.