MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 '11 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 '11 at 16:18
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 '11 at 17:57
fedja, that's a good point. Like I said, I didn't actually do the algebra. – Michael Lugo Apr 8 '11 at 13:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.