assume that we have two (or more) convex hulls in the plane and we want merging them. but the convex hull result has minimum perimeter. is any algorithm available for this?

CodePudding user response：

You can run any optimized convex hull algorithm on the boundary point of two convex hulls, you should get a new convex hull covering both of the previous ones. To maintain the convex property, there will be a unique resultant convex hull, so the minimum perimeter should not be a constraint.

CodePudding user response：

Split all K hulls in upper and lower hulls. Now you have 2K sorted sequences of vertices. Merge the upper and lower sequences separately, using a K-way merge. This is done in time O(N log(K)) where N is the total number of vertices.

Now two Graham scans give the global hulls in time O(N).

[This is an adaptation of the monotone-chain algorithm.]