As a beggining to convex hull algorithms lecturer introduced the structure which it's called "Hierarchy Structure".
Hierarchy Structure: in every given convex hull there is a maximum size convex hull which is can contain maximum only one edge of adjacent vertices and all other edges should be from non-adjacent vertices of the given convex hills.
For example, on the picture below, we have the set $<P_{0},P_{1},P_{2}>$
$h_{i}$ - is the number of vertices of convex hull $P_{i}$, $h_{i} \leq \frac{h_{i+1}+1}{2}$
According to definition there is at most log$n$ such convex hulls, where $n$ is the number of vertices of a given convex hull.
Unfortunately I haven't found precise definition of Hierarchy Structure in textbooks of computational geometry. If anyone familiar with the above definition, please send me a link.
Having defined the Hierarchy Structure I have to prove the following lemma.
Lemma1. If $P$ is a convex hull and $P'$ in the next convex hull after $P$ in Hierarchy Structure, $q$ is the point in $P \setminus P'$, in this case two tangent line from $q$ to $P'$ are going through two adjacent vertices of convex hull $P'$ (see the picture below). And a polytop that is formed from adding $qx$ and $qy$ to $P'$ and deleting $xy$ from $P'$ is actually convex.
The problem is I cannot figure out how to prove it rigorously. The prove of the second part of the lemma seems very obvious, if $q$ is the external point to $P'$ so adding this point will form new convex hull. But how to show that needed operations is deleting $xy$ and adding $qx$ and $qy$. Also it seems like the prove of second part should help to prove the first part. If you have any idea how to prove this lemma correctly I'll appreciate if you share it with us.
Thanks!