Abstract: We present a sub-linear algorithm to compute the set of back-facing polygons in a polyhedral model. The algorithm partitions the model into hierarchical clusters based on the orientations and positions of the polygons. As a pre-processing step, the algorithm constructs spatial decompositions with respect to each cluster. For a sequence of back-face computations, the algorithm exploits the coherence in view-point movement to efficiently determine if it is in front of or behind a cluster. Due to coherence, the algorithm's performance is linear in the number of clusters on average. We have applied this algorithm to speed up the rendering of polyhedral models. On average, we are able to cull almost half the polygons. The algorithm accounts for 5 - 10% of the total CPU time per frame on an SGI Indigo2 Extreme. The overall frame rate is improved by 40 - 75% as compared to the standard back-face culling implemented in hardware.