[Solved]: If a point is a vertex of convex hull

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(n\log 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