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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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, 2018 at 2:09
  • $\begingroup$ Indeed, it is about the boundary of a not always convex object. $\endgroup$
    – Dima Pasechnik
    Nov 3, 2018 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, 2018 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, 2018 at 12:42
  • $\begingroup$ Thanks, these are very helpful references. $\endgroup$
    – Dima Pasechnik
    Nov 3, 2018 at 22:16

Your Answer

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

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