Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there something tricky about that? Or I should use some of the standard convex hull algorithms ?
I mean, I don't see anything different between creating convex hull for a set of points and creating convex hull for non-overlapping convex polygons (2D)?

share|cite|improve this question

If this is in 2D, Yes, you should just use a standard algorithm. The Graham scan is perfect for your application, as it will not waste much time beyond sorting. You can find code all over the web, including my own here.

share|cite|improve this answer
How about ? (: – Kiril Kirov Jun 7 '11 at 19:08

Creating the convex hull of a finite set of points takes $\Omega(n\log n)$ steps in worst case, which means $n\log n$ is a lower bound for the complexity of every algorithm that solves this problem.

Otherwise you could sort random points (1D) faster that $n\log n$ by calculating the convex hull (2D) of the points $(p_i,p_i^2)$

Construction of the convex hull of a simple polygon is possible in $O(n)$ as shown for example by Preparata and Shamos in 1985:

Construction of the convex hull of a convex polygon is actually possible in $O(1)$ because the convex hull of a convex polygon is the polygon itself.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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