Delaunay triangulation can be used in reconstruction two-and-a-half dimensional maps. Even from very limited input. Here you can read a paper about an algorithm which combines delaunay surfacing with weighted average sampling to get the best of both worlds.
0.497M
2½D map reconstruction
For additional information.
