Convex-hull of a star shaped polygon in O(n)

Question

I'm trying to develop an algorithm to find a convex hull of a star shaped polygon in $O(n)$ time. The specific problem, which is also described here, is as follows:

A polygon $P$ is star-shaped if there exists a point $p$ in the interior of $P$ that is in the shadow of every point on the boundary of $P$. The set of all such points $p$ is called the kernel of $P$.

Given an $n$-vertex, star-shaped polygon $P$ specified by its vertices in counterclockwise order, how to compute convex hull of this polygon in linear time.

According to these slides (slide $64$), it's really possible to find such a convex hull in linear time using Graham's Scan. This result is given as a corollary. This means that we probably need only the "scan" part of the Graham's Scan algorithm to solve this problem.

---

Imagine we have the following star-shaped polygon $P$:

and lets pick the point with the lowest $y$ coordinate of $P$, i.e., $p_2''$. If I'm not wrong, start from there, the steps applied would be:

1. Pick the next vertex, i.e., $p_3''$.

2. Lets consider the vertex $a$. We check if $p_2''p_3''a$ is a left or right turn, by using the cross product $(p_3'' - p2'') \times (p_3''- a)$. Since it's a left turn, we pick $a$.

3. We now consider $p_3''ab$. It's also a left turn, so we pick $b$.

4. We now consider $abc$. We also have a left turn, so we pick $c$.

5. Consider $bcp_1'$. It's a left turn, so we alsp pick $p_1'$.

6. $cp_1'p2'$ is a right turn. Thus we need to remove from the stack $p_1'$. Thus, so far we have included the following vertices in the $CH(P) = p_2'', p_3'', a, b, c, p_2'$.

7. We consider $cp_2'p_3' = cp_2'p_1''$ (just notation). It's a left turn, so we should include $p_3' = p_1''$. $CH(P) = p_2'', p_3'', a, b, c, p_2', p_3'$.

8. We now consider $p_2'p_3'p_2''$. It's a right turn, so we should remove all points which create a right turn with $p_2''$, i.e. , $p_3' = p_1''$, but also $p_2'$, because of $cp_2'p_2''$. So, now our final $$CH(P) = p_2'', p_3'', a, b, c, p_2''$$

The (literally) Graham's scan seemed to work in this instance, but I would not know for sure if it would work in general.

---

I tried to think about other ideas to solve this problem, since I was not sure this Graham's scan is correct, but it was mostly because I was not considering as initial point the one with the lowest $y$ coordinate.

If Graham's scan is enough to solve this problem, then the order given of the vertices, as specified in the problem above, must be related to one of the necessary orderings of the vertices required in a usual Graham's scan. I'm talking about sorting the points by polar angle in counter-clockwise around the initial chosen point $p_0$ or about sorting the points according to their $x$ value.

---

I would appreciate an explanation of the corollary in the slide I'm mentioning above, provided it's really a corollary.

Answer 1

Graham scan for a convex hull works if you have an ordering of points $a_1,a_2,...a_N$ such that you have a sequence $p_1 < p_2 <...< p_k$ where your convex hull is $a_{p_1}, a_{p_2},...,a_{p_k}$ of which it is not possible to have a winding number greater than $1$.

In general for any polygon $P$ this might not work, but for a star shaped polygon, you could observe that from the point $p$ visible to all points, in counter-clockwise order, will be have the aforementioned property.