Computing the right tangent of two convex hulls

Question

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:

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

Answer 1

The paper of Preparata and Hong says:

We let $l_A$ and $r_A$ be two points of A such that $x_2(l_A) = \min_i {x_2(a_i)}$ and $x_2(r_A) = \max_i{x_2(a_i)}$; similarly $l_B$ and $r_B$ are defined in B.

and:

Without loss of generality, we shall also assume that $r_A = a_1$ and $r_B = b_1$.

So, in this notation, vertices in your two polygons will be numbered differently:

$$A=((1.2,1),(0.2,0.2),(0.3,1.3))$$ $$B=((3,2),(2,2),(2,3))$$

In simple words, the algorithm starts from rightmost vertices on both polygons and continues clockwise potentially until leftmost vertices - so, only lower sides of both polygons will be involved. Tangential vertices $(0.2,0.2)$ and $(3,2)$ will be found.

This paper has been published long time ago, and since then this algorithm has been clarified and simplified. The newest version of it starts from the rightmost vertex on the left polygon and the leftmost vertex on the right polygon, and continues clockwise for the left polygon and counterclockwise for the right polygon (to find lower tangential line). Also they usually check a vertex location relative to a line using the dot product instead of calculating and comparing slopes - because the tangential vertex has to have both its neighbors on the same side of the tangential line. For more information, pictures and code - please see this monograph, Section 3.8.