# computing the boundary of a union of polytopes

Let $$P_1,\dots ,P_m\subset \mathbb{R}^n$$ be $$m<\infty$$ convex polytopes in $$\mathbb{R}^n$$, and $$U:=\bigcup_{j} P_j$$ their set-theoretic union. What algorithms are known for computing the boundary $$\partial U$$ of $$U$$?

Note that $$U$$ would not always be convex, might have a nontrivial fundamental group, etc.

A naive algorithm I can think about would start from $$\partial P_1$$, intersect each facet of $$P_2$$ with it, obtaining $$\partial (P_1\cup P_2)$$, etc. A less naive point of view might involve working with measures supported on $$P_j$$'s and inclusion/exclusion in some way.

Any references on this sort of questions?

## 1 Answer

Not a direct answer, but may help with: "Any references on this sort of questions?"

Computing the convex hull of the union of two polytopes $$P_1 \cup P_2$$ is NP-hard:

Tiwary, Hans Raj. "On the hardness of computing intersection, union and Minkowski sum of polytopes." Discrete & Computational Geometry 40, no. 3 (2008): 469-479. Author preliminary PDF download.

But the computation is polynomial for special polytopes:

Balas, Egon. "On the convex hull of the union of certain polyhedra." Operations Research Letters 7, no. 6 (1988): 279-283. Journal link.

Conforti, Michele, Marco Di Summa, and Yuri Faenza. "Balas formulation for the union of polytopes is optimal." arXiv:1711.00891 (2017).

Added. Specializing to $$\mathbb{R}^3$$, there is an algorithm that constructs the boundary of the union, which runs in $$O(k^3 + kn \log k \log n)$$ expected time, where $$k$$ is the number of polyhedra and $$n$$ is the total number of faces:

Aronov, Boris, Micha Sharir, and Boaz Tagansky. "The union of convex polyhedra in three dimensions." SIAM Journal on Computing 26, no. 6 (1997): 1670-1688. Journal link Aronov, Sharir, Tagansky.

Subsequently there was a specialized extension to $$\mathbb{R}^4$$:

Aronov, Boris, Alon Efrat, Vladlen Koltun, and Micha Sharir. "On the union of κ-round objects in three and four dimensions." Discrete & Computational Geometry 36, no. 4 (2006): 511-526. Journal link.

• The question seems to be about the boundary of set theoretical union, rather than convex hull. – Alexandre Eremenko Nov 3 '18 at 2:09
• Indeed, it is about the boundary of a not always convex object. – Dima Pasechnik Nov 3 '18 at 9:26
• A related to the complexity question - how about the case of fixed dimension (e.g. $n=3$). – Dima Pasechnik Nov 3 '18 at 9:27
• @DimaPasechnik: Yes, I realize that my original post doesn't directly answer your question. Incidentally, it is also NP-hard to compute $P_1 \cap P_2$. – Joseph O'Rourke Nov 3 '18 at 12:42
• Thanks, these are very helpful references. – Dima Pasechnik Nov 3 '18 at 22:16