Approximate a curve with limited number of samples

Preface: We have an analogue measurement device that changes its behaviour with temperature. We use an environmental chamber and cycle through a range of -20°C and 120°C to find out how the many components fluctuations with temperature affect the measurement, and then program the micro-controller with a table of its own behaviour so it can take account for this before it outputs a result. The micro controller is fairly low powered and has a lot of other things to do, so we keep the recreation simple and use linear interpolation and a lookup table with 151 values [-25, 125] which stores the point we sampled at that temperature.

I'm trying to find out if we can minimise any errors by using by using delta-sigma to optimise the space in memory (the limitations of which shouldn't be an issue in this application) and then store a difference in temperature since the previous point along with a difference in output from the previous point.

Once we can freely choose where to place sample points, we should be able to reduce the number of points taken to represent areas that have a low rate of change and add additional points to areas that have a high rate of change over temperature, effectively giving us a close overall approximation of the original sampled data.

Example of current method, which may contain large errors at rapidly changing locations

Example of hopefully new method, which can prioritise where to place sample points for interpolation later

I know this kind of optimisation is possible, as I've used exactly 10 samples in each of the above two images, and it's clear that the image I eyeballed to priorite the sample points creates a much better approximation than the image where I evenly spaced the samples.

Question: Is there a means to determine the best spacing (which a fixed number of samples) for minimising the errors in the recreated approximation?

Note: we've used polynomail approximation in a previous version, and took a look at some other methods such as sum of sine, but none of them proved to be a close enough approximation for our data so we went with a strait forward interpolation from a look up table. You can't get a much better approximation than an actual data sample. But now I'm curious if we can optimise the spacing of the sample points to further improve accuracy.

Meta: Feel free to play with the tags or make suggestions to improve the question. I'm not very comfortable with terminology in mathematics. Although is someone can explain an equation or algorithm I should be able to code it.