A polygon
P
is star-shaped if there exists a pointp
in the interior ofP
that is in the shadow of every point on the boundary ofP
. The set of all such pointsp
is called the kernel ofP
.
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.