USING TOPOLOGICAL SWEEP TO EXTRACT THE BOUNDARIES OF REGIONS IN MAPS REPRESENTED BY REGION QUADTREES

A variant of the plane-sweep paradigm known as topological sweep is ad apted to solve geometric problems involving two-dimensional regions wh en the underlying representation is a region quadtree. The utility of this technique is illustrated by showing how it can be used to extract the boundaries of a map in O(M) space and O(M alpha(M)) time, where M is the number of quadtree blocks in the map, and alpha(.) is the (ext remely slowly growing) inverse of Ackerman's function. The algorithm w orks for maps that contain multiple regions as well as holes. The algo rithm makes use of active objects (in the form of regions) and an acti ve border. It keeps track of the current position in the active border so that at each step no search is necessary. The algorithm represents a considerable improvement over a previous approach whose worst-case execution time is proportional to the product of the number of blocks in the map and the resolution of the quadtree (i.e., the maximum level of decomposition). The algorithm works for many different quadtree re presentations including those where the quadtree is stored in external storage.