Dot diffusion has been proposed as a way of combining the strengths of ordered dithering and error diffusion to create a parallelizable halftoning technique.However, dot diffusion pays a price in image quality in order to achieve parallelizability.Space-filling curves have been used to improve error diffusion.We show that by combining dot diffusion with a space-filling curve traversal technique, a parallelizable halftoning technique results that does not pay a cost in image quality.This new technique we call space diffusion.

An adaptation of the quadtree data structure that represents polygonal maps (i.e., collections of polygons, possibly containing holes) is described ina manner that is also useful for the manipulation of arbitrary collections of straight line segments. The gol is to store these maps without the loss of information that results from digitization, and to obtain a worst-case execution time that is not overly sensitive to the positioning of the map. A regular decomposition variant of the region quadtree is used to organize the vertices and edges of the maps. A number of related data organizations are proposed in an iterative manner until a method is obtained that meets the stated goals. The result is termed a PM (polygonal map) quadtree and is based on a regular decomposition point space quadtree (PR quadtree) that stores additional information about the edges at its terminal nodes. Algorithms are given for inserting and deleting line segments from a PM quadtree. Use of the PM quadtree to perform point location, dynamic line insertion, and map overlay is discussed. The PM quadtree is compared conceptually to the K-structure and the layered dag with respect to typical cartographic data. An empirical comparison of the PM quadtree with other quadtree-based representations for polygonal maps is also provided.

The ``line quadtree'' data structure hierarchically represents a region and its boundary. Based on the standard quadtree, each node in this structure stores adjacency information as well. While line quadtrees use the same amount of space as standard qaudtrees, they facilitate several region processing algorithms. In particular, we describe efficient algorithms for boundary and superimposing two maps encoded as line quadtrees.

Results of a study are summarized in which quadtrees were used to encode the regions in three map overlays representing a small area in northern California. Programs were then written to perform various analysis and manipulation tasks on the quadtree-encoded regions. Data is provided on the compactness of the encodings and the efficiency of the programs.