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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.