<p>If you assume all the points are in the convex hull and you can find a point that is inside the convex hull, then you can find the order of the points in $O(n log n)$ time by taking the angle from the interior point to every point in your set and sorting this.</p>

<p>Once you know the order of the points, the angle from each point to the next point in the sequence should be monotonic. This forms a necessary condition and, I think, a sufficient one. </p>

<p>Getting the interior point is left as an exercise for the reader.</p>

<hr>

<p>Edit: As a fist pass at a simple demonstration of $O(n log n)$ being a hard bound, to show that a point is/isn't on the convex hull requires knowing the adjoining points (possibly an arbitrary number of them) and finding that requires either sorting all the points or (this is speculation) examining more than a constant number of other points.</p>

CC BY-SA 2.5
2010-09-27T02:26:48.730Z
You probably misread his o(n log n) as O(n log n) much as I did. Anyway, the algorithm you outlined is gift wrapping in embryonic form. You don't actually need to use an interior point; you can use a point on the boundary, e.g. a point with minimal x coordinate.
Per Vognsen
CC BY-SA 2.5
2010-09-27T04:47:10.677Z
@Per Vognsen: My algo, still needs to sort the points so it's only $O(n log n)$ (BTW, is $o()$ an exclusive bound?)
BCS
CC BY-SA 2.5
2010-09-27T05:11:51.593Z
The point is that there are plenty of convex hull algorithms that run in O(n log n). Your algorithm is basically plain old gift wrapping. He was asking for something faster, e.g. linear time. See the other responses.
Per Vognsen
CC BY-SA 2.5
2010-09-27T13:05:39.023Z
@Per Vognsen: Yeah, I got that from your fist comment, OTOH it might be faster by a constant than a full convex hull solution.
BCS
CC BY-SA 2.5
2010-09-27T13:20:54.983Z
Regarding your edit, if you could look at the accepted answer above yours, you'll see that the problem is equivalent to element uniqueness, which has an O(n log n) lower bound.
Per Vognsen
CC BY-SA 2.5
2010-09-27T14:49:26.150Z
@Per Vognsen: I read that one, twice (once before I posted and now again) I still don't see how the mapping from convex hull to uniqueness works (but will edit my edit in light of that). OTOH unless the OP was just interested in $o(n log n)$ solutions rather than wanting the fastest, my answer may be relevant.
BCS
CC BY-SA 2.5
2010-09-27T14:57:54.097Z
@BCS: I am afraid that you have some misunderstanding about Sariel Har-Peled’s answer.  The reduction is from uniqueness to convex position testing, not the other direction.  That is, Sariel (and JeffE) stated out that if you are given a set of numbers and want to test uniqueness, you can convert it to a set of points and use any algorithm for convex position testing.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-27T15:23:45.017Z
@Tsuyoshi Ito, Ah, now I get it.
BCS
CC BY-SA 2.5
2010-09-27T02:15:25.517Z
2010-09-27T14:51:46.053Z
2010-09-27T14:51:46.053Z
BCS
<p>Thats seems unlikely, at least in the comparison/algebraic tree models. Definition first:</p>

<p>A point set $P$ is in convex position if no point of $P$ can be written as a convex combination of the remaining points of $P$.</p>

<p>Now, deciding if a set of $n$ numbers are all distinct takes $\Omega(n \log n)$ time (this is known as UNIQUENESS). Given such a set of $n$ numbers $X$, map them to the set of points
$$
P = \{ (x, x^2) | x \in X\}.
$$
If there is no repeated number, then the points are in convex position.</p>

<p>If there is a repeated number, then this repeated number corresponds to a point that can be written as a convex combination of the remaining points. Namely, the points are not in convex position.</p>

<p>Namely, deciding if a point set is in convex position is as hard as UNIQUENESS.</p>

CC BY-SA 2.5
2010-09-25T05:14:37.740Z
There is a variant of this reduction that doesn't produce duplicate points.  Let X[1..n] be a set of integers; testing whether all the elements of X are distinct still requires Ω(n log n) time in the algebraic decision tree model.  Now replace each integer $X[i]$ with the point $(X[i], X[i]^2+i/n^2)$.  If the original array X has any duplicates, the resulting points will have at least one point in the interior of the convex hull; otherwise, the points are in convex position.
Jeffε
CC BY-SA 2.5
2010-09-25T05:31:50.283Z
@Babis: Jeff's reduction works when duplicate points are not allowed. The points generated by the reduction are unique no matter what the initial array is.
Vinayak Pathak
CC BY-SA 2.5
2010-09-25T05:37:19.303Z
We thus get that the number of the corners of the convex hull is equal to n if and only if no two points have the same x-coordinate. Thanks a lot, initially I thought that it should be easier than sorting.
Babis Tsourakakis 
CC BY-SA 2.5
2010-09-25T05:38:45.680Z
Thanks Vinayak, I had not seen Jeff's reduction since it was posted at the same time when I was writing the previous comment which I substituted with the above
Babis Tsourakakis 
CC BY-SA 2.5
2010-09-27T13:23:31.783Z
Suresh, I disagree with the phrase "standard model". That's exactly what the Word RAM is :) It is the model that most closely matches a real computer and that we use to analyze algorithm in most of TCS. Geometry has pleaded an exception to use the Real RAM so that we don't need to deal with precision issues. But that's not "the standard model."
Mihai
CC BY-SA 2.5
2010-09-27T18:42:04.443Z
@Mihai - fixed to comparison/algebraic tree model.
Sariel Har-Peled
CC BY-SA 2.5
2010-09-25T05:01:08.190Z
2010-09-27T18:41:16.703Z
2010-09-27T18:41:16.703Z
Sariel Har-Peled
<p>Assume that you are given a set of n points in the plane and you want to check whether they form a convex n polygon, i.e., if they all lie on the convex hull. I was wondering if anyone knows how to do this in o(nlogn) time, i.e., without computing the CH. </p>

CC BY-SA 2.5
2010-09-25T04:11:40.267Z
You can compute the convex hull in O(n log n) time. Do you mean if it's possible to do it in _less_ time than that?
Per Vognsen
CC BY-SA 2.5
2010-09-25T04:16:57.080Z
yes, I believe that there should be some linear time algorithm for this problem. but i do not know how
Babis Tsourakakis 
CC BY-SA 2.5
2010-09-25T04:19:21.490Z
In that case, please correct your question's body and title.
Per Vognsen
CC BY-SA 2.5
2010-09-25T04:22:15.383Z
He wrote o(nlogn) not O(nlogn), so his question is correct.
Shiva Kintali
CC BY-SA 2.5
2010-09-25T04:23:24.553Z
Sorry, I should have read more carefully.
Per Vognsen
CC BY-SA 2.5
2010-09-25T04:24:26.367Z
I use the little o notation so the question still holds as is
Babis Tsourakakis 
CC BY-SA 2.5
2010-09-27T05:23:59.043Z
It makes me frown a bit to see sorting of numbers (or equivalently convex hulls of Cartesian points) stated as taking Θ(n log n) time without an explicit statement of what model of computation you're using. Comparison sorting takes Θ(n log n) time but the comparison model doesn't even allow hulls to be computed at all. They're both still Θ(n log n) time for algebraic decision trees (as the accepted answer shows), but faster in models of computation that more closely resemble actual computers.
David Eppstein
CC BY-SA 2.5
2010-10-14T17:23:29.330Z
Also, here is a related reference http://www.cs.huji.ac.il/~benor/AlgCompTrees83.pdf
Babis Tsourakakis 
<cg.comp-geom>
Testing whether a set of n points in the plane form a convex n polygon in o(nlogn) time
Babis Tsourakakis 
# Testing whether a set of n points in the plane form a convex n polygon in o(nlogn) time

(Asked by: username_0 on 2010-09-25)

Assume that you are given a set of n points in the plane and you want to check whether they form a convex n polygon, i.e., if they all lie on the convex hull. I was wondering if anyone knows how to do this in o(nlogn) time, i.e., without computing the CH.

**Tags:** cg.comp-geom
> **Comments:**
> **username_1**: You can compute the convex hull in O(n log n) time. Do you mean if it's possible to do it in _less_ time than that?  
> **username_0**: yes, I believe that there should be some linear time algorithm for this problem. but i do not know how  
> **username_1**: In that case, please correct your question's body and title.  
> **username_2**: He wrote o(nlogn) not O(nlogn), so his question is correct.  
> **username_1**: Sorry, I should have read more carefully.  
> **username_0**: I use the little o notation so the question still holds as is  
> **username_3**: It makes me frown a bit to see sorting of numbers (or equivalently convex hulls of Cartesian points) stated as taking Θ(n log n) time without an explicit statement of what model of computation you're using. Comparison sorting takes Θ(n log n) time but the comparison model doesn't even allow hulls to be computed at all. They're both still Θ(n log n) time for algebraic decision trees (as the accepted answer shows), but faster in models of computation that more closely resemble actual computers.  
> **username_0**: Also, here is a related reference http://www.cs.huji.ac.il/~benor/AlgCompTrees83.pdf  

---

## 2 answers

### Answer by username_6 on 2010-09-25. Score: 17 | Accepted answer

Thats seems unlikely, at least in the comparison/algebraic tree models. Definition first:

A point set $P$ is in convex position if no point of $P$ can be written as a convex combination of the remaining points of $P$.

Now, deciding if a set of $n$ numbers are all distinct takes $\Omega(n \log n)$ time (this is known as UNIQUENESS). Given such a set of $n$ numbers $X$, map them to the set of points
$$
P = \{ (x, x^2) | x \in X\}.
$$
If there is no repeated number, then the points are in convex position.

If there is a repeated number, then this repeated number corresponds to a point that can be written as a convex combination of the remaining points. Namely, the points are not in convex position.

Namely, deciding if a point set is in convex position is as hard as UNIQUENESS.

> **Comments:**
> **username_7**: There is a variant of this reduction that doesn't produce duplicate points.  Let X[1..n] be a set of integers; testing whether all the elements of X are distinct still requires Ω(n log n) time in the algebraic decision tree model.  Now replace each integer $X[i]$ with the point $(X[i], X[i]^2+i/n^2)$.  If the original array X has any duplicates, the resulting points will have at least one point in the interior of the convex hull; otherwise, the points are in convex position.  
> **username_8**: @Babis: Jeff's reduction works when duplicate points are not allowed. The points generated by the reduction are unique no matter what the initial array is.  
> **username_0**: We thus get that the number of the corners of the convex hull is equal to n if and only if no two points have the same x-coordinate. Thanks a lot, initially I thought that it should be easier than sorting.  
> **username_0**: Thanks Vinayak, I had not seen Jeff's reduction since it was posted at the same time when I was writing the previous comment which I substituted with the above  
> **username_9**: Suresh, I disagree with the phrase "standard model". That's exactly what the Word RAM is :) It is the model that most closely matches a real computer and that we use to analyze algorithm in most of TCS. Geometry has pleaded an exception to use the Real RAM so that we don't need to deal with precision issues. But that's not "the standard model."  
> **username_6**: @Mihai - fixed to comparison/algebraic tree model.  

---

### Answer by username_4 on 2010-09-27. Score: -1

If you assume all the points are in the convex hull and you can find a point that is inside the convex hull, then you can find the order of the points in $O(n log n)$ time by taking the angle from the interior point to every point in your set and sorting this.

Once you know the order of the points, the angle from each point to the next point in the sequence should be monotonic. This forms a necessary condition and, I think, a sufficient one.

Getting the interior point is left as an exercise for the reader.

---

Edit: As a fist pass at a simple demonstration of $O(n log n)$ being a hard bound, to show that a point is/isn't on the convex hull requires knowing the adjoining points (possibly an arbitrary number of them) and finding that requires either sorting all the points or (this is speculation) examining more than a constant number of other points.

> **Comments:**
> **username_1**: You probably misread his o(n log n) as O(n log n) much as I did. Anyway, the algorithm you outlined is gift wrapping in embryonic form. You don't actually need to use an interior point; you can use a point on the boundary, e.g. a point with minimal x coordinate.  
> **username_4**: @Per Vognsen: My algo, still needs to sort the points so it's only $O(n log n)$ (BTW, is $o()$ an exclusive bound?)  
> **username_1**: The point is that there are plenty of convex hull algorithms that run in O(n log n). Your algorithm is basically plain old gift wrapping. He was asking for something faster, e.g. linear time. See the other responses.  
> **username_4**: @Per Vognsen: Yeah, I got that from your fist comment, OTOH it might be faster by a constant than a full convex hull solution.  
> **username_1**: Regarding your edit, if you could look at the accepted answer above yours, you'll see that the problem is equivalent to element uniqueness, which has an O(n log n) lower bound.  
> **username_4**: @Per Vognsen: I read that one, twice (once before I posted and now again) I still don't see how the mapping from convex hull to uniqueness works (but will edit my edit in light of that). OTOH unless the OP was just interested in $o(n log n)$ solutions rather than wanting the fastest, my answer may be relevant.  
> **username_5**: @BCS: I am afraid that you have some misunderstanding about Sariel Har-Peled’s answer.  The reduction is from uniqueness to convex position testing, not the other direction.  That is, Sariel (and JeffE) stated out that if you are given a set of numbers and want to test uniqueness, you can convert it to a set of points and use any algorithm for convex position testing.  
> **username_4**: @Tsuyoshi Ito, Ah, now I get it.  

---

