A new approach is presented for partitioning an image database by classifying and indexing the convex hull shapes and the concavity features of regions. The result is a significant increase in image search and retrieval speed. The convex hull is first determined using a novel and efficient approach based on the geometrical heat differential equation. Next, the convex hull is represented by a triad of boundary shapes and other parameters as viewed from three viewpoints. This information enables the regions in the image database to be divided into 344 convex hull classes. Concavity information, obtained using a boundary support parameterization, further partitions the database. Since a given query must now be compared only to shapes of the same class, searching is much faster. Both theoretical background and practical results are discussed.