Skip to main content
3 of 4
TeX; consistent capitalisation
LSpice
  • 12.9k
  • 4
  • 45
  • 69

Boolean operation on n dimensional polyhedron

A polyhedron in $R^n$ is defined by a set of half-planes: $P = \{x \in R^n \mid Ax - b < 0\}$.

Given a set of polyhedra in $R^n$, $ P_1, P_2, \dotsc, P_k$, is there an algorithm/implementation that calculates the combination of all $k$ polyhedra $ P_1\cup P_2 \cup \dotsb \cup P_k$, and gives the final shape's vertices and facets (extreme points and faces)?

Or is this an ongoing research topic?

After a search online, I found most algorithms are focusing on 2D and 3D polyhedra. CGAL has implementations on boolean operations of 2D and 3D Nef Polyhedra (https://doc.cgal.org/latest/Nef_2/index.html and https://doc.cgal.org/latest/Nef_3/index.html).