4
$\begingroup$

My question deals with the algorithm of computing the convex hull in 2D by Preparata.

Let us assume we have two sets, $A$, $B$, of points in the plane. Let $CH(A)$ and $CH(B)$, denote the convex hulls of the two sets, A and B respectively. And suppose that $y(a) < y(b)$ for all $a \in A$ and $b \in B$.

Let $CH(A) = \{a_{0},...,a_{n}\}$ and $CH(B) = \{b_{0},...,b_{m}\}$ such that we have indexed both sets to be clockwise sequences.

Now there is $k$ such that $x(a_{k}) = \text{max}(x(a_{i}))$ for all $ 0\leq i \leq n$ and $j$ such that $x(b_{j}) = \text{max}(b_{l}))$ for all $0 \leq l \leq m$.

Now our first task is to find the common tangents of $CH(A)$ and $CH(B)$. My question is about finding the right tangent.

Now let $\alpha_{i, i+1}$ denote the slope of the two points $a_{i}$ and $a_{i+1}$; $\beta_{j,j+1}$ denote the slope of the two points $b_{j}$ and $b_{j+1}$; $\gamma_{i,j}$ denote the slope of the two points $a_{i}$ and $b_{j}$ (all indices are taken mod n and mod m).

Suppose $a_{i^{*}}$ and $b_{j^{*}}$ denote the two endpoints of the right tangent. Preparata states the two endpoints of the right tangent satisfy the following:

(1) $i^{*} > 0: \alpha_{i^{*},i^{*}+1} < \gamma_{i^{*},j^{*}} \leq \alpha_{i^{*}-1,i^{*}}$

(2) $i^{*} = 0 : \alpha_{0,1} < \gamma_{1,j^{*}}$

(3) $j^{*} > 0: \beta_{j^{*},j^{*}+1} \leq \gamma_{i^{*},j^{*}} < \beta_{j^{*}-1,j^{*}}$

(4) $j^{*} = 0: \beta_{1,2} \leq \gamma_{i^{*},1}$

However I found that if we take $A = \{(0.2,0.2),(0.3,1.3),(1.2,1)\}$ and $B = \{(2,2),(2,3),(2,3)\}$ then we have the following picture:

enter image description here

We see that the left endpoint (i.e. the endpoint in $CH(A)$) of the right common tangent should be $(0.2,0.2)$ and the right endpoint (i.e. the endpoint in $CH(B)$) should be $(3,2)$ .

However the criterion that Preparata claims does not select $(0.2,0.2)$ as the left endpoint, since it does not satisfy $(2)$, but $(0.3,1.3)$. Why does this occur? Does Preparata's algorithm have some other claim that it needs to be correct?

Here is a link to the original paper:

http://www.cs.jhu.edu/~misha/Spring16/Preparata77.pdf

The section I'm referring to is called "Merge Algorithm for Two-Dimensional Sets."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.