1
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ The question seems to be about the boundary of set theoretical union, rather than convex hull. $\endgroup$ – Alexandre Eremenko Nov 3 '18 at 2:09
  • $\begingroup$ Indeed, it is about the boundary of a not always convex object. $\endgroup$ – Dima Pasechnik Nov 3 '18 at 9:26
  • $\begingroup$ A related to the complexity question - how about the case of fixed dimension (e.g. $n=3$). $\endgroup$ – Dima Pasechnik Nov 3 '18 at 9:27
  • $\begingroup$ @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$. $\endgroup$ – Joseph O'Rourke Nov 3 '18 at 12:42
  • $\begingroup$ Thanks, these are very helpful references. $\endgroup$ – Dima Pasechnik Nov 3 '18 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.