Interpolation: given N points (x1,y1), (x2,y2), ..., (xN,yN), find a polynomial P(x) of degree=N-1 so that yk=P(xk). Pixerpolation: There are N "one-dimensional pixels" which each are finite subintervals of the real x-axis, and the goal is to find a polynomial P(x) whose value AVERAGED over the Kth pixel, equals y_K. I'll assume these intervals are ADJACENT, i.e.they tile one big interval. Solution: Pixerpolation can be done in essentially the same time & space (as a function of N) as ordinary interpolation. Simply interpolate the INTEGRATED P-value at all the N+1 pixel endpoints, using a degree=N polynomial, then take its derivative. (Integral=interval length times average value...) What about if we drop the adjacent-pixels assumption? Then it is not so easy anymore. One could do it by solving an NxN linear system, e.g. by order N^3 time using Gauss's method. One also could do an interval-averaged analogue of Lagrange interpolation. That is, precompute polynomials of degree=N-1 which have average=1 on pixel K, but average=0 on (and exactly one root within) each of the other N-1 pixels. Anyhow, it clearly can be done in a polynomial number of operations, but it is not obvious how fast. One would hope for a method taking O(N * (logN)^2) operations, which would equal the time bounds known for ordinary interpolation via clever algorithm tricks. But that might be a vain hope.