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 limits 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 very large problem. The objective of the LP is to create as "good" a surface as possible. This formulation is new, as previous methods did not aim to minimise an objective function. If the desired surface has only slope limitations, the resulting drape surface must be constrained in the first derivative. Such a drape surface is readily constructed using the Lifting Algoritlun. It is shown that the Litling Algorithm is both exact and has great speed advantages. Some numerical results confinning exacmcss and speed are presented, as is the algorithm's analogy to a flow network method. An enhanced lifting method with a better order of complexity is also proposed and tested numerically. In most practical situations a drape surface is required which has both first and second derivatives constrained. If only a cut through such a surface is considered, the problem can be solved with relative ease by exploiting its nctwork~Jike structure. This method fonns the basis of one of the preferred heuristics developed later. It was not possible to generalise this method to a full two~dimensional drape surface. A commercially available LP package fares better in finding the optimal solution. Several heuristic methods were examined. first a general heuristic method based on a lifting approach was developed. This was followed by a method using repeated application of the method used for sections (the Alternating One-dimensional Dual Algorithm ["AODA"]). Three heuristics based on thimbles were also designed. Thimbles are caps whose first and second derivatives are acceptable and which are placed over local infeasibilities in the topography The work ends with a chapter comparing the efficiency of various heuristics and comparing the results obtained using a number of test datasets. It was fOLmd that heuristic methods provide acceptable drape surfaces and that the choice lies between speed and accuracy, with a previously designed smoothing method being the fastesl and the AODA the most accurate and quick enough. / Operations Research / D.Phil.

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 limits 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 very large problem. The objective of the LP is to create as "good" a surface as possible. This formulation is new, as previous methods did not aim to minimise an objective function. If the desired surface has only slope limitations, the resulting drape surface must be constrained in the first derivative. Such a drape surface is readily constructed using the Lifting Algoritlun. It is shown that the Litling Algorithm is both exact and has great speed advantages. Some numerical results confinning exacmcss and speed are presented, as is the algorithm's analogy to a flow network method. An enhanced lifting method with a better order of complexity is also proposed and tested numerically. In most practical situations a drape surface is required which has both first and second derivatives constrained. If only a cut through such a surface is considered, the problem can be solved with relative ease by exploiting its nctwork~Jike structure. This method fonns the basis of one of the preferred heuristics developed later. It was not possible to generalise this method to a full two~dimensional drape surface. A commercially available LP package fares better in finding the optimal solution. Several heuristic methods were examined. first a general heuristic method based on a lifting approach was developed. This was followed by a method using repeated application of the method used for sections (the Alternating One-dimensional Dual Algorithm ["AODA"]). Three heuristics based on thimbles were also designed. Thimbles are caps whose first and second derivatives are acceptable and which are placed over local infeasibilities in the topography The work ends with a chapter comparing the efficiency of various heuristics and comparing the results obtained using a number of test datasets. It was fOLmd that heuristic methods provide acceptable drape surfaces and that the choice lies between speed and accuracy, with a previously designed smoothing method being the fastesl and the AODA the most accurate and quick enough. / Operations Research / D.Phil.