Before revision:  For convex polyhedra in R^3, the method yields an algorithm running in O((p-q+1)n^{ 13/ 5 +\epsilon }  n(\log\log n)^{1/6} } + p^4 ) expected time.
After revision:  For convex polyhedra in R^3, we get an algorithm running in O((p-q+1)n^{ 13/ 5 +\epsilon } n(\log\log n)^{1/6} } + p^4 ) expected time.