Convex Hull in Hierarchy Structure

Question

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!

Answer 1

The operation you describe is equivalent to a step in the incremental algorithm for constructing a convex hull algorithm. Take $q$ to be a new point and $P'$ is your partial hull just before processing $q$. Since $q$ is external to $P'$ and does not evict any existing hull vertices. It must be the case that the resulting polygon is convex.

Proving convexity can be done in two ways.

1. Show that the hull is an intersection of half-planes. Since P' is already convex, all you have to do is to show that the each of the two support lines passing through $qx$ and $qy$ divide the plane into two half-planes, one of which is empty.

2. Another way to go is that show that any point in the resulting polygonal area can be constructed as a convex combination of the vertices. You might want to proceed to show that the extension to $P'$ does not introduce a point that couldn't be defined as a convex combination of the vertices -- an argument by contradiction should be straight-forward.