We have seen a variety of interpolation techniques: These include Hermite interpolation, cubic spline interpolation and Bezier Curves.

Suppose we have obtained an approximating curve. If one data point is removed, what is the number of operation required to updat the curve for each of the three cases?

In each case, select one of the following as your answer and explain your reasoining: O(1), O(logn), O(sqrt(n), O(n), O(nlogn) or O(n^2) operations.

Question

We have seen a variety of interpolation techniques: These include Hermite interpolation, cubic spline interpolation and Bezier Curves. 

Suppose we have obtained an approximating curve. If one data point is removed, what is the number of operation required to updat the curve for each of the three cases?

In each case, select one of the following as your answer and explain your reasoining: O(1), O(logn), O(sqrt(n), O(n), O(nlogn) or O(n^2) operations.

babalooo · Answer

Assume there are n data points, the new point is inserted somewhere near the middle of the interpolating curve and that we choose the optimal algorithm

I just don't get this question to begin with

anonymous · Answer

For the initial set of data points you have an approximating curve, meaning you have analysed the data points and come up with a set of constants. When removing a data point, how many operations (addition, etc) do you need in terms of n to update your constants?

For starters, is it even possible to 'update' your constants or do you need to compute them all over again?