7
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @JeffE, is there a mistake in my idea? You can see it if you hover the mouse over the part below the second paragraph. $\endgroup$ – Kaveh May 20 '12 at 18:42
  • $\begingroup$ I figured it out. (I had a different solution in mind.) $\endgroup$ – JeffE May 20 '12 at 18:43
  • $\begingroup$ @JeffE, I should have written an in place of the, will fix it in a second. :) $\endgroup$ – Kaveh May 20 '12 at 18:46
  • 2
    $\begingroup$ @JeffE, I am curious, what was your idea? $\endgroup$ – com May 25 '12 at 5:49
7
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.