Calculate the convex hull of a star polygon in O(n) time

Question

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.

For example, in a pentagram, the center points can be reached from the shadow of all the points lying on the boundary of P if the light source is considered to be infinity. A star polygon is not necessarily star in shape.

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.

I am getting no clue in this question. The algorithms I can think of are O(n * log(n)). I am not able to understand how to use this extra bit of information.

Answer 1

I'm assuming this is homework of some sort, whether assigned for a class or for your own study, so I'll just give you a hint:

The key here is the counterclockwise order, or more accurately, the fact that vertices are in a consistent order.

Given three consecutive vertices p₁, p₂ and p₃, consider the two vectors defined by:

V₁ = (p₁ - p₂) and
V₂ = (p₃ - p₂).

What do we know about the cross product V₁ x V₂? How will this value be different if p₂ is on the boundary of the polygon versus in the center? The correct answer to this should divide our vertices into two classes. How will these classes be different for clockwise rather than counterclockwise orderings?