13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Per Vognsen Sep 25 '10 at 4:11
  • $\begingroup$ yes, I believe that there should be some linear time algorithm for this problem. but i do not know how $\endgroup$ – Babis Tsourakakis Sep 25 '10 at 4:16
  • 4
    $\begingroup$ He wrote o(nlogn) not O(nlogn), so his question is correct. $\endgroup$ – Shiva Kintali Sep 25 '10 at 4:22
  • 1
    $\begingroup$ I use the little o notation so the question still holds as is $\endgroup$ – Babis Tsourakakis Sep 25 '10 at 4:24
  • 4
    $\begingroup$ 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. $\endgroup$ – David Eppstein Sep 27 '10 at 5:23
17
$\begingroup$

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.

$\endgroup$
  • 12
    $\begingroup$ 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. $\endgroup$ – Jeffε Sep 25 '10 at 5:14
  • 1
    $\begingroup$ @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. $\endgroup$ – Vinayak Pathak Sep 25 '10 at 5:31
  • $\begingroup$ 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. $\endgroup$ – Babis Tsourakakis Sep 25 '10 at 5:37
  • $\begingroup$ 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 $\endgroup$ – Babis Tsourakakis Sep 25 '10 at 5:38
  • 2
    $\begingroup$ 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." $\endgroup$ – Mihai Sep 27 '10 at 13:23
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Per Vognsen Sep 27 '10 at 2:26
  • $\begingroup$ @Per Vognsen: My algo, still needs to sort the points so it's only $O(n log n)$ (BTW, is $o()$ an exclusive bound?) $\endgroup$ – BCS Sep 27 '10 at 4:47
  • $\begingroup$ 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. $\endgroup$ – Per Vognsen Sep 27 '10 at 5:11
  • 1
    $\begingroup$ 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. $\endgroup$ – Per Vognsen Sep 27 '10 at 13:20
  • 2
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Sep 27 '10 at 14:57

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.