The construction of drape surfaces with constrained first derivatives

The need to construct optimal drape surfaces arises in airborne geophysical surveys where it is necessary to fly a safe distance above the ground and within the performance of the aircraft used, but as close as possible to the surface. The problem is formulated as an LP with constraints at every point of a grid covering the area concerned, yielding a huge problem. The lifting algorithm is suggested. This is a surprisingly simple algorithm which starts with the drape surface at ground level and lifts it one point at a time. Only points which too low relative to one or more of their neighbours are considered and they are lifted just enough to bring them into kilter with their neighbours. It is shown that the lifting algorithm is both exact and has great speed advantages. Some numerical results confirming exactness and speed are presented. An enhanced method with better complexity is proposed and tested numerically.