The notion of staircase separator, introduced in [2], greatly facilitates the design of divide-and-conquer algorithms for problems on rectangles. We generalize the concept of staircase separator to k-perfect staircase separator, namely a set of staircase separators which partitions a set S of n axis-parallel, rectangles into k subsets of (almost) equal size. We derive an optimal O(logn) time parallel algorithm for computing a k-perfect staircase separator, using O(n) processors on the CREW PRAM model of computation. For a special case, where k = 2, this result provides a new bound of \(\left\lceil {\frac{n}{2}} \right\rceil\), in compared to \(\left\lceil {\frac{{7n}}{8}} \right\rceil\) in [2], on the quality of staircase separators for sets of rectangles.