Given two convex hulls $C_1, C_2$ in $\mathbb{R}^2$ or $\mathbb{R}^3$, it is known how to merge the two convex hulls into a a third convex hull $C$ (the convex hull of the points in $C_1, C_2$) in time $O(|C_1|+|C_2|)$ (Where $|C_i|$ is the number of vertices + faces of the convex hull polytope).

For constant $d\geq 4$, what is known on the complexity of merging two convex hulls in $\mathbb{R}^d$?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.