The digital medial axis transform (MAT) is a representation of binary images as a union of squares of maximal odd side lengths. This representation (which can be a list of pairs of square centers and side lengths) can be quite storage efficient for certain objects. The point of this paper is that it is also reasonably computationally efficient since some interesting geometric properties can be calculated in n log n time, where n is the number of squares. The authors discuss boundaries and perimeters, connected components, areas and moments, derived sets (union, intersection, and complement), and conversion between representations.

The paper makes repeated use of the notion of a segment tree, which is a data structure for describing a discrete interval by repeated division into approximate halves. Sets of subintervals can then be represented by appropriate labeling of the nodes of the segment tree in an efficient fashion.

A warning is appropriate: It is not easy to follow this paper without first studying its references. For example, at the beginning of the description of the connected components algorithm, the priority search tree data structure is introduced (with a reference to a 1982 Xerox PARC research report [1]), but based on the material in the paper under review, I could not understand what a priority search tree is supposed to be.