Are there any known types of bounded polyhedra, which exist in all Euclidean dimensions, and are are closed under intersection, rotation and relative complement? In other words, I am looking for a set of polyhedra $P$, where $p \in P \subset \mathbb{R}^d$, and P is closed under rotation, intersection and relative complement.
I think this is unlikely, so I am also interested to see if there is any $P$ where the intersection or complement of any two elements in $P$, can be efficiently and exactly decomposed into a finite number of elements of $P$.
An arbitrary bounded convex polyhedron $p$ is the intersection of finitely many half-planes. Since $p$ is bounded, each of those half-planes can be replaced with a scaled, rotated copy of your favourite polyhedron $q$, by aligning one of its faces with the half-plane and then enlarging it to contain $p$. So any $p$ is the intersection of rotated, sufficiently large copies of $q$. Shrink the whole configuration to return the $q$'s to their original size, and we obtain a small copy of $p$.
In other words, if your collection of polyhedra is nonempty (it contains $q$, where $q$ was arbitrary), it also contains sufficiently small copies of all possible bounded convex polyhedra.