Separation of a preprocessed polyhedron and a plane
Theorem 3.1 requires that the hierarchical representation of $P$ is compact.  One of the requirements for compactness is that the degree of $r_i$ in $P_{i-1}$ is bounded by a constant.  See the bottom of page 3.

The definition and construction of the Dobkin-Kirkpatrick hierarchy is much more explicit in their earlier papers (references [9,10,11] in the paper you're reading).  I strongly recommend reading them first.