Abstract This paper presents a methodology for determining a set of part orientations on a coordinate measuring machine (CMM), given part descriptions and tolerance information. A part frequently needs more than one orientation for inspection, and therefore it is important to determine a set of part orientations such that all tolerances under consideration can be inspected. The methodology utilizes the visibility map (VMap) to represent accessible directions from which measurements for inspecting a tolerance can be performed. The concept of VMap dimensionality is proposed to provide the basis for clustering VMaps as well as to facilitate the clustering procedure. The presented heuristic groups dimensioned VMaps into a set of disjoint VMap clusters, providing a reasonably small number of part orientations. The algorithms are implemented in C++ and tested on a SGI workstation.