Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

2 Answers 2

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|improve this answer
    
How about cgm.cs.mcgill.ca/~orm/mergech.html ? (: –  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: http://cgm.cs.mcgill.ca/~athens/cs601/Preparata.html

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|improve this answer

Your Answer

 
discard

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.