I am working on a game with large outdoor terrains, and I have a heightmap-based terrain system set up. The heightmaps are generally quite detailed, eg 2049x2049 (for 2048x2048 quads), and I do dynamic LOD on the GPU. However, for the physics this detail is not always a good idea. My players (vehicles) get stuck on small bumps etc. and the terrain physics are quite heavy. This is why I would like to scale down the original heightmap to something like half the resolution, or a fourth of the resolution or whatever the level in question works best with, and use this lower detail heightmap for the physics mesh.
What algorithm should I use for something like this? I should be fast enough so that I can run it when the level loads, and generally "work well" for terrain physics meshes. Do I just calculate the average over the nearby vertices or is there some better way to do it?