# Algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane

I am trying to find an algorithm to compute the convex hull of a set of $$m$$ possibly intersecting convex polygons in the plane, with a total of $$n$$ vertices. Let $$h$$ denote the number of vertices on the boundary of the desired convex hull. The algorithm should run in $$\mathcal O(mh+n)$$ time

• how are the polygons given? Mar 21, 2019 at 20:58
• as a list of vertices ordered clock-wise. Mar 22, 2019 at 9:42

You probably know that merging $$m{=}2$$ convex polygons can be accomplished in linear time, $$O(n)$$. And there is the Kirkpatrick–Seidel output-size sensitive algorithm that achieves $$O(n \log h)$$.