Is there a reason you choose to use a polynomial function instead of a piecewise linear function?
From your empirical data it looks like no more than 5 linear sections (see red lines in figure below) would be needed to characterize the curve quite well.
This would significantly cut down on the number of computations needed to return a result, and in this case it look like it might even more accurately fit the input data.
