Clifford A. Shaffer
Department of Computer Science, Virginia Polytechnic Institute and State University
Quentin F. Stout
Computer Science and Engineering, University of Michigan
Abstract: Optimal linear time algorithms are given for computing the chessboard (l∞, rook) distance transform for both pointer-based and linear quadtree representations. Comparisons between algorithmic styles for the two representations are made. Both versions of the algorithm consist of a series of tree traversals.
Keywords: quadtrees, hierarchical data structures, chessboard distance, rook, l∞ distance, medial axis transform, QMAT, top-down traversal, neighbored traversal, algorithms, computer science
Complete paper. This paper appears in Computer Vision, Graphics, and Image Processing: Image Understanding 54 (1991), pp. 215-223.
|Copyright © 2005-2016 Quentin F. Stout|