Convex Hull of the Union of Convex Objects in the Plane: an Adaptive Analysis.
Jérémy Barbay, Eric Chen · 2008
We prove a tight asymptotic bound of Θ(δ log(n/δ)) on the worst case computational complexity of the convex hull of the union of two convex objects of sizes summing to n requiring δ orientation tests to certify the answer. For more convex objects, we prove a (non optimal) asymptotic bound of O(δ ∑ k i=1 log(ni/δ)) on the worst case computational complexity of the convex hull of the union of k convex objects of respective sizes (n1,..., nk) requiring δ orientation tests to certify the answer. Our algorithms are deterministic, they use portions of the convex hull of input objects to describe the final convex hull, and take advantage of easy instances, such as those where large parts of two objects are horizontally or vertically separated. 1