Two well-known algorithms for polyline simplification are the Douglas Peucker and Visvalingam algorithms.
The Douglas Peucker algorithm uses a recursive divide-and-conquer approach. It starts by drawing a straight line from the first point to the last point. Then it finds the intermediate point that is furthest away from the straight line and deems this the "most important" and splits the polyline into two halves at that point. This process is repeated on both halves until the distance of the intermediate point is below a certain threshold, after which all points on that sub-polyline are thrown away since they have a negligible impact on the overall shape.
The Visvalingam algorithm works from the inside-out. It starts by computing the area of the triangle formed by each consecutive three points along the polyline. Then the midpoint of the triangle with the least area is thrown out since those three points are the closest to colinear and the area of triangles on either side are recomputed. The process continues until all remaining triangles are above a certain threshold.
The Douglas Peucker algorithm is O(n^2) and if a min-heap is used for the Visvalingam algorithm to keep track of the triangle with the smallest area then its complexity is O(n log(n)) - making it a more attractive choice when the number of points gets very large.
This simulation shows the results of both algorithms side-by-side when applied to the Seven Climbs of Death bicycle ride in State College, Pennsylvania. The original route is shown in gray, the simplified route in black, and the discrepancy is shaded in red.
To get the desired number of points instead of using a threshold, this simulation uses the algorithms to sort the points in each polyline by importance, then extract the N most important points. The Douglas-Peucker algorithm implementation is extracted from the source for onthegomap.com and the Visvalingam algorithm implementation is from bost.ocks.org/mike/simplify.