Convex-hull of a star shaped polygon in O(n)
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 &lt; p_2 &lt;...&lt; 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.