Separation of a preprocessed polyhedron and a plane

Question

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.

Answer 1

Answer updated and rewritten from scratch.

You are given a polytope $P$. Run the Dobkin-Kirkpatric hierarchy on P. This gives you a sequence of polytops $P_1 \subseteq P_2 \subseteq \ldots \subseteq P_k = P$. Let assume you would like to find the closest point on $P$ to a query point $q$. The basic algorithm starts by computing the closest point $c_1$ to $q$ on $P_1$, then it considers all the new regions (tents) adjacent to $c_1$, find the closest point $c_2$ to $q$ in these new regions, and continue in this fashion till we reach $P_k$.

Now, if $c_i$ is on an edge, then there is no problem - only two tents might touch this edge, or only one of them might cover the edge. As such, updating $c_{i+1}$ from $C_i$ in this case takes constant time.

So the problem is when $c_i$ lies on a vertex of high degree, because then the number new tents adjacent to it when moving to $P_{i+1}$ might be large. To overcome this, we are going to simulate a large degree vertex as a collection of vertices having low degree. In particular, at each stage, if $c_i$ lies on a vertex $v$, we are going to remember two consecutive edges $e_i, e_i'$ adjacent to $v$, such that the closest point to $q$ in $P_{i+1}$ lies on a tent that is either adjacent or covers one of these two edges. As such, we can do the required computation in constant time.

So we remain with the problem of how to keep track of these two edges as we climb up.

To do that, precompute for every vertex $v$ of $P$ a tangent direction $t_v$. Let $Q_i(v)$ be the convex polygon that is the vertex figure of $v$ for the polygon $P_i$ (with the plane defining the vertex figure has normal in the direction of $t_v$). Conceptually, $Q_1(v), Q_2(v), ..., Q_k(v)$ behaves like a 2d DK hierarchy. If the closest point on $Q_i(v)$ to $q$ lies on a vertex $w$ then this corresponds to $v$ and an adjacent edge $e$ in $P_i$, where the edge $e$ intersects the plane of the vertex figure at $w$. If the closest point on $Q_i(v)$ to $q$ lies on an edge $e'$, then you remember the two adjacent edges of $P_i$ that define the two vertices of $e'$ (here $e'$ belongs to $Q_i(v)$).

And now we are done... Indeed, if $c_{i+1}$ is also on $Q_{i+1}(v)$ then we can updated it in constant time (since this is just a 2d DK hierarchy). If on the other hand $c_{i+1}$ is no longer on $Q_{i+1}(v)$ then it must belong to a new tent that is adjacent or covers the previous point $c_{i}$. In either case, we can update it in constant time.

Answer 2

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.

Answer 3

In case somebody would still be interested by the question: the snag in the Dobkin Kirpatrick explanation has also been pointed out in Barba and Langerman's Optimal detection of intersections between convex polyhedra.

They observe in the paper (SODA 2015 version, not arxiv) that O'Rourke's Computational Geometry in C, chap 7 already details a workaround (which is essentially Sariel's answer). The SODA paper also introduces an alternative solution; defining a variant of the DK hierarchy in which each vertex has bounded degree.