Convex hull for convex polygons

Question

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)?

Answer 1

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.

Answer 2

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.