# 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.

• I really wonder that if I offer a bounty in the description of which I say that JeffE's answer is not clear to me and in a comment to his answer I specify my issue with it, then why do people keep on upvoting his answer without answering my question? Also, I wonder, would his answer get the bounty automatically? Dec 20, 2011 at 17:22
• an upvote indicates that the answer provides something of value, which it did ! just not exactly what you wanted. indeed, the answer you needed appeared to be a refinement of the general suggestion. Also, why worry about someone else's upvotes ? Dec 22, 2011 at 23:47

## 3 Answers

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.

• Updated answer. See if it makes any sense now. This is the way I think about this data-structure. It might have no relation to what is in the paper. Dec 22, 2011 at 15:53
• I understand now, thank you! So the trick is that we choose the tangent directions at the beginning and keep them unchanged the whole time! I have deleted my previous comments that were related to your old answer. Thanks once more! Dec 22, 2011 at 17:34
• Yes. Happy to help! Dec 22, 2011 at 21:08

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.

• I think that they guarantee that the degree of vertices in $P_{i-1}\setminus P_i$ is bounded. I do not see how you could make sure the degree of $r_i$ is bounded. If e.g. you have a polyhedron where two vertices are connected to every vertex, then how can you start? Dec 5, 2011 at 17:57
• With one of the other vertices, which all have degree 4. (In fact, with an independent subset of the degree-4 vertices.) The point $r_i$ is a vertex of $P_{i-1}$ but not a vertex of $P_i$. Dec 6, 2011 at 13:29
• So there is the misunderstanding. I think that $r_i$ is a vertex of $P_i$ as well in the algorithm that I have described, notably the one closest to $S$. Am I wrong? Dec 7, 2011 at 13:59
• This seems to be one of these standard but tedious general position assumption. If you do not care about running time, you can always replace a vertex of degree $d$ by two extremely close vertices of degree $d/2 + 3$ (if you insist on triangular faces). Repeat this till all the vertices till all the degrees are smaller than 10. Dec 19, 2011 at 14:40
• @Sariel: I was thinking the same but then why would the process end? Notice that when we delete a vertex, then its neighbors might not form a face, so we might have to add new edges, in fact, we might have to increase the degree of a vertex. Dec 20, 2011 at 7:54

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.