Stretching meshes to fit other meshes

I want to create a map composed of square tiles using plane meshes, in which I can raise or lower individual tiles and the neighbouring tiles will stretch so that their neighbouring edges / corners will still be connected with the raised tile. A good example is Popolous: The beginning. I tried modifying the meshes in the Update method, but it's too CPU intensive, and while reducing the vertex count works, if I understand correctly it will limit my ability to attach objects to separate parts of the tile. I tried using joints, but they don't stretch the mesh.

Is there another method that can provide real-time transformations like this? I considered compute shaders, but I'd prefer to try something with a simpler API before I attempt that.