Variations on sweep algorithms: efficient computation of extended viewsheds and class intervals
Marc J. van Kreveld · 1996
Two novel applications of the plane sweep paradigm are demonstrated, namely, for the computation of extended viewsheds on gridded DEMs and for class interval selection on TIN-based DEMs. In both cases, the efficiency of the plane sweep algorithm is significantly better than a straightforward approach. The algorithms are presented by first giving the plane sweep method as a general approach that requires some ingredients to make it work well. Adaptations to minimize additional storage use are also presented. 1 Introduction One of the most important paradigms in the design of geometric algorithms is that of sweeping. In a plane sweep algorithm, an imaginary horizontal line traverses the plane from top to bottom, during which some property of the data is computed (a more clear description is given later). Plane sweep algorithms have been used for a variety of geometric problems like map overlay, Voronoi diagrams and hidden surface removal. The plane sweep approach is described in most te...