Problem Detail: The exercise is
Given a set of point $S$ and a point $p$. Decide in $O(n)$ time if $p$ is a vertex of convex polygon formed from points of $S$.
The problem is I am a little bit confused with time complexity $O(n)$. The more naive solution would be to construct convex polygon in $O(nlog n)$ and test if $p$ is one of the vertices.
Asked By : com
Answered By : Kaveh
Hint: the point $p$ is a vertex of the convex hall iff there are two half-lines from it such that all points fall inside the angle created by them. Here is an idea for an algorithm based on this hint:
Design an algorithm with two variables $q$ and $r$ (input points). The algorithm will examine each of the input points and will update $q$ and $r$ so that all points checked so far fall inside the wedge $angle qpr$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1940
