Variations on sweep algorithms Efficient computation of extended viewsheds and classificati.pdf

Variations on Sweep Algorithms:ecient computation of extended viewsheds and class intervalsMarc van KreveldDept. of Computer Science, Utrecht UniversityThe NetherlandsE-mail: marc@cs.ruu.nlAbstractTwo novel applications of the plane sweep paradigm are demonstrated, namely,for the computation of extended viewsheds on gridded DEMs and for class intervalselection on TIN-based DEMs. In both cases, the eciency of the plane sweepalgorithm is signicantly better than a straightforward approach. The algorithmsare presented by rst giving the plane sweep method as a general approach thatrequires some ingredients to make it work well. Adaptations to minimize additionalstorage use are also presented.1 IntroductionOne of the most important paradigms in the design of geometric algorithms is that ofsweeping. In a plane sweep algorithm, an imaginary horizontal line traverses the planefrom top to bottom, during which some property of the data is computed (a more cleardescription is given later). Plane sweep algorithms have been used for a variety of geometricproblems like map overlay, Voronoi diagrams and hidden surface removal. The planesweep approach is described in most textbooks on computational geometry [34, 37, 40].Implementation of plane sweep algorithms usually is straightforward.In computational geometry, the plane sweep approach has become a standard techniquein the design of ecient algorithms. On the other hand, in GIS literature the plane sweeptechnique is known|in particular for map overlay [4, 28, 32]|but not yet a standardtechnique. Certainly, its use hasnt been recognized to its full extent. The purpose of thispaper is to give two new applications of the plane sweep method, showing its importanceand versatility once more. Both applications address a problem in the important GIScapability of geographical analysis.The rst plane sweep algorithm that will be described solves various problems in view-shed analysis, such as the computation of extended viewsheds [18, 1