This paper proposes an image/scene representation called the augmented medial axis transform (AMAT) that offers advantages of both object centered (e. g. , medical axis transform), and viewer centered (e. g. , quadtree) representations. AMAT consists of the basic MAT along with a graph that connects the centers of the MAT primitives that overlap or are adjacent. The average degree alpha of a node in the graph is much smaller than the number N of squares in the basic MAT. Most computations take O(N**2) time for the MAT, but only O( alpha N) for AMAT.