# How To Interpolate I don't care about complex methods which result in accurate data. Keep it simple, stupid. So I will post only simple methods. When you think about simplicity, you can agree that linearity is the simplest. And more degree is not essentially better because of Runge's phenomenon. Suppose that the data set is f(0) = 1 f(1) = 3 f(2) = 2 f(3) = 5 I will explain with the xy-plane, but you can apply to any other spaces. ## Nearest Neighbor f(x) = 1 ( 0 <= x < 0.5) = 3 (0.5 <= x < 1.5) = 2 (1.5 <= x < 2.5) = 5 (2.5 <= x <= 3 ) This is the simplest method. You almost don't need to compute. I think that this method would be good if ### 1. The data is categorical Think of text antialiasing. The text should be dark and the background should be white. Not in between like grey. This method is fantastic for categorical data like that. P.S. It seems that anime-style drawings are categorical data. Nearest neighborhood method results in better quality. It makes sense because those use only few colors. ### 2. The function is at least uniformly continuous If it's Lipschitz continuous, best. To explain what those mean, (these are not rigorous definitions though) * Lipschitz continuous: The slope is bounded. dy <= K * dx for some K>=0. * Uniformly continuous: The slope doesn't have to be bounded, but dy itself doesn't go inf. (inf = infinity) Ex) sqrt(x) isn't Lipschitz continuous since the slope goes inf as x->0. But it is uniformly continuous since dy itself doesn't go inf. It's just that dy is much larger than dx where x->0. Ex) 1/x isn't uniformly continuous since dy goes inf as x->0. Thus it isn't Lipschitz continuous too. So these basically mean that if x1, x2 are near, then f(x1), f(x2) are near, GLOBALLY. If it's locally, that's just the definition of continuity. This method is good for that kind of situations. ### 3. You don't give a fuck about the quality and just want speed But remember, this method makes the function into a mosaic. Or a pixel art. Well, pixel arts are good actually :) ## Linear f(x) = 2x + 1 (0 <= x < 1) = -x + 4 (1 <= x < 2) = 3x - 4 (2 <= x <= 3) so that f(0)=1, f(1)=3, f(2)=2, f(3)=5. For a bilinear version, f(x0, y0) = f(x0)_y=y0 = f(y0)_x=x0 where f(x)_y=y0: X -> F, f(y)_x=x0: Y -> F, f(x)_y=y0 = f(x, y0), f(y)_x=x0 = f(x0, y). F means a Field. Like C, R, Zp. This means making two 1-variable functions, not one 2-variable function, by fixing x=x0 or y=y0. And both are piecewise linear like f(x) above. This is simple and best. If the data is not categorical, this might be the best option. The error depends on f'', i.e. the curvature. So the error is larger when the function is curvier. If the data is categorical, like text antialiasing above, this method might result in blurry outcome. Because it uses grey too. Not only black & white. But on average, this results in better outcomes than nearest neighbor method. And there are still not many calculations. ## Least square Use only when there is definitely a pattern. I don't want to explain all those basic(?) linear algebra. So I'll just write the method. Suppose you have an overdetermined (more equations than variables) system, Ax = b (as a matrix equation). Then multiply A* (Muh duality). (A*)Ax = (A*)b Then multiply the inverse. x = [(A*)A]^-1 * (A*)b This is the optimal solution. Ex) Since the data set (x,f(x)) was (0,1), (1,3), (2,2), (3,5) above, set |1 0| |1| |1 1| |3| |c'| A = |1 2| , b = |2|, x = |c | . (A is a Vandermonde matrix) |1 3| |5| Then with some calculations, |4 6 | |c'| |11| |6 14| * |c | = |22| ((A*)Ax = (A*)b) [4 6 | 11] [6 14 | 22] (just do some Gaussian elimination) [1 0 | 1.1] ~ [0 1 | 1.1] (I did it for you guys) so c'=1.1, c=1.1. Therefore f(x) = cx + c' = 1.1 * x + 1.1 is the line which minimizes the sum of squared residuals (~errors) . So use this line to interpolate. There are things like the error following a normal distribution, &c. If you want to know those things, read some regression analysis books. Also, you can use least square for nonlinear cases. But keep it simple and stay linear until you can't. You can still use those piecewise linear functions of linear interpolation.