This paper presents a novel PRT-based method that uses precomputed visibility cuts for interactive view-dependent relighting under all-frequency environment maps and arbitrary BRDFs. Our method is inspired by Lightcuts and we parameterize distant environment lighting onto uniformly distributed sample points on the unit sphere. Using a binary tree structure of the sample points, we precompute and approximate each vertex's visibility function into clusters that we call the precomputed visibility cuts. These cuts are computed with bounded approximation error and confined cluster size using iterative refinement. At runtime, a GPU-based relighting algorithm quickly computes the view-dependent shading color by accessing a dynamically built cluster of the lighting, the precomputed visibility cuts, and a direct evaluation of the dynamic BRDF using the average direction represented by each lighting cluster. Compared to existing PRT techniques, our method guarantees uniform sampling of the lighting, requires no precomputed BRDF data, and can be easily extended to handle one-bounce glossy indirect transfer effects in real-time.