Algorithm for approximating linear-interpolated curve Goal
Given a curve defined by a set of (x, y) coordinates with linear interpolation, we want to find the best approximation using a smaller set of points (w/ linear interpolation) that fall along a predefined grid. The number of points and the grid are chosen up front and are static. The following invariants must be held:

*

*Our approximation must not go below the original curve at any point. (Both curves are generated by sorting by the x-axis values and drawing lines between neighbors).

*The grid origin is (0, 0) and generated from an x-step and y-step values.

*Our approximation must fully cover the original curve.  This means that our first (x1) and last (x2) x-axis values are forced by the set of (x, y) coordinates of the original curve and x-axis step, and that our possible y-axis values are bounded below by the minimum y-step multiple that is >= min y-axis value found in the original curve (derived from first invariant).

*Y-axis values must fall between [0, 255].

*The best approximation will be the one that has the smallest area between the approximation and original curve.

Example
# Example arguments provided to algorithm
# curve - Contains 25 points, sorted by x-axis ascending, w/ linear interpolation between neighbors
original_curve = [(450, 38), (462.5, 28), (481.25, 28), ..., (887.5, 22)]
# Our answer must use points that fall along the grid generated by the below steps
x_step = 25
y_step = 1
# Number of points allowed in the approximation
num_points = 5

# We can compute the following boundaries based on the arguments
max_x_on_grid = 900
min_x_on_grid = 450
max_y_on_grid = 255
# The full dataset is not shown above, but the minimum y-axis value is 9, which is equal to a multiple of y_step
min_y_on_grid = 9

# We want our approximation to use 5 points, which means we can immediately determine the following
answer = [(450, ?), (?, ?), (?, ?), (?, ?), (900, ?)]

What I've tried
Originally I thought I might be able to do an exhaustive search, but the number of possibilities is way too high.
Number of possible x-axis selections = C(22, 3)
Number of possible y-axis selections = P(245, 5) (w/ replacement)
Number of possibilities = C(22, 3) * P(245, 5) = 1540 * 882,735,153,125 = 1.3594121e+15

I'm certain there is a more intelligent algorithm I could use.  I've implemented the genetic algorithm before, and I imagine it would get a good result, but I would like to get the best result. I've tried to play with the idea of starting at the max_y_on_grid and doing some type of search + backtracking from there, but I thought I would ask in case anyone has already done this.

Due to time constraints and our inability to come up with a better solution, we ended up using the genetic algorithm to compute our approximation.  It was able to generate a better approximation then any of our other attempts, and it did so efficiently (rust implementation took 1-15 seconds).  Here is a list of the genetic parameters we used if anyone is curious.
Population size: 1000
Mutation Rate: 1%
Elitism: 10%
Selection: Tournament
    Tournament size: 4
    Tournament probability: 0.75

