If a point is a vertex of convex hull

Question

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.

Answer 1

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$.

Answer 2

The problem is to find a line that passes through $p$ and has all the other points in $S$ on one side. This is a two-dimensional linear-programming problem, so it can be solved in $O(n)$ time using textbook geometric algorithms. But let me describe a self-contained solution.

---

To simplify notation, translate all the points so that $p$ is the origin $(0,0)$, and let $Q = S\setminus\{p\}$. Then we want to determine if there is a real number $m$ such that either (1) $y < mx$ for all $(x,y)\in Q$ or (2) $y > mx$ for all $(x,y)\in Q$. In the first case, $p$ is a vertex of the upper hull of $S$; in the second case, $p$ is a vertex of the lower hull of $S$. I'll describe an algorithm for the first case; the other case is symmetric.

If any point in $Q$ lies directly above $p$ (that is, if any point in $Q$ has coordinates $(0,y)$ for some $y>0$), then $p$ cannot lie on the upper hull. It is easy to check this condition in $O(n)$ time.

So assume no points in $Q$ lie directly above $p$. The $y$-axis splits $Q$ into two subsets $L$ (left) and $R$ (right). Points in $L$ have negative $x$-coordinates, and points in $R$ has positive $x$-coordinates. (Points directly below $p$ don't matter; just ignore them.) Let $$ m_L = \min_{(x,y)\in L} \frac{y}{x}, \quad M_R = \max_{(x,y)\in R} \frac{y}{x}, \quad \text{and} \quad m = \frac{m_L + M_R}{2}. $$ Now there are three cases to consider:

• If $m_L < M_R$, then every point in $Q$ lies strictly below the line $y = mx$, so $p$ is a vertex of the upper hull.

• If $m_L = M_R$, then the line $y=mx$ passes through a point in $L$ and a point in $R$, and no point in $Q$ is strictly above that line. So $p$ lies on an edge of the upper hull, but it is not a vertex.

• If $m_L > M_R$, then at least one point in $L$ and at least one point in $R$ lie strictly above the line $y=mx$. So $p$ lies strictly below the upper hull.

It is easy to compute $m_L$ and $M_R$ in $O(n)$ time. We don't actually need to compute $m$.