Separation of a preprocessed polyhedron and a plane I have serious trouble understanding one step in the paper of Dobkin and Kirkpatrick about the separation of polyhedra. I am trying to understand this version: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf

It argues that after we know the best separation of $P_{i}$ and $S$, realized by $r_i$ and $s_i$, we can find the best separation of $P_{i-1}$ and $S$ in $O(1)$ steps. This is done in the following way. We take the plane parallel to $S$ through $r_i$ and cut $P_{i-1}$ into two parts with it. On one side, the closest point to $S$ is $r_i$ and on the other we have an ``elementary'' polyhedron that we can check in $O(1)$ time. My problem is - how do we find this elementary polyhedron? Note that the degree of $r_i$ in $P_{i-1}$ might be unbounded.

In the pdf to prove Thm 5.1 from page 9, they use Thm 3.1 from page 4, which makes the whole thing harder to follow.
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.