We routinely face this in the audio world when drawing waveforms. You typically have on the order of 10-100k samples per second, durations of 10s-1000s of seconds, and pixel widths of on the order of 1-10k pixels.

Bresenham's is one algorithm historically used to downsample the data, but a lot of contemporary audio software doesn't use that. In Ardour (a cross-platform, libre, open source DAW), we actually compute and store min/max-per-N-samples and use that for plotting (and as the basis for further downsampling.