Linear Time Distance Transforms for Quadtrees

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.

 

Quentin's Home Copyright © 2005-2017 Quentin F. Stout