Suppose I have a function $F(x)$ that returns a scalar given a scalar input $x$. Since $F(x)$ happens to be expensive or inconvenient to compute, I would like to replace it with a lookup table approximation. That way I only compute values at a few points, and then can estimate values of the function at many more points using linear interpolation of the table values.
Rather than choose breakpoints a priori (e.g. equally-spaced values of $x$), I'd like to be able to specify either a) the number of entries, or b) the (perhaps approximate) maximum permissible error of the approximation, and then have an algorithm select the optimal breakpoints to populate the lookup table. These points would be optimal in the sense that (e.g.) they minimize mean square error in some given range $[a,b]$.
Let's say I can also compute derivatives of $F$ if needed. I'm specifically interested in the case where $F(x)$ is a CDF (so the function is monotonic and the range is 0 to 1).
This seems like a fairly generic problem, but I'm struggling to find a good solution.
The problem you describe is Optimal Scalar Quantization. For a fixed number of entries in your table, finding the optimal configuration is difficult since the function being optimized is non-convex and generally has many local (non-optimal) local minimum. However, Lloyd's method is a simple strategy which reduces the quantization error, approaching a local minimum and is widely sufficient in practice.
Here are some slides and notes on scalar quantization. One standard reference on the mathematical underpinning of this problem is:
Du, Qiang; Faber, Vance; Gunzburger, Max, Centroidal Voronoi tessellations: Applications and algorithms, SIAM Rev. 41, No. 4, 637-676 (1999). ZBL0983.65021.
The biggest challenge implementing LLoyd's method will be how you perform quadrature (and how many function evaluations that requires to get a reasonable result).