In the course of my research (radio engineering), I need to solve the following problem, for which I do not feel well equipped.
I would like to calculate the union of polychora (4-polytopes, bounded regions of 4D-space).
In 1D, this is overlapping lines. Easy.
In 2D, we have overlapping polygons, again this is relatively simple see https://stackoverflow.com/questions/2667748/how-do-i-combine-complex-polygons.
In 3D it starts to get a bit harder, I knew blender (3D animation software) has an algorithm that does this and thus I went down the path of constructive solid geometry algorithms, mainly used in 3D modelling (CAD) software. There appear to be two options, a) use a BSP tree, b) use equations of planes and regions and do a discrete sampling of space testing against each shape. See this for a discussion. https://stackoverflow.com/questions/2002976/constructive-solid-geometry-mesh
My actual problem is to now extend this into 4D space, taking the union of a bunch of 4-polytopes, and, in the end (for those interested, or who might have a way to sidestep my 4-polytope problem altogether) to check if these combined regions of 4d space completely cover a unit tesseract with its bottom, left, far, something?! corner at [0,0,0,0]. If not, what regions are not covered?
The route I am currently considering is to discretise the unit tesseract into small (enough) tesseracts, check each of them against my various 4-polytopes and just do a boolean OR operation to get a combined shape from the union of all the 4-polytopes. This is a bit of a hack though, (looping over 4d space might be slow). Also, my actual problem doesn't suit this approach very well, because my X, Y discretisation will probably want to be quite different to my Z, W discretisation, and really I don't want to faff around with that.
I'd be interested to hear from,
a) anybody who has an analytical solution to getting the union of 4-polytopes in some format (e.g. vertex and adjacency list).
b) anybody who would be able to suggest some analogies from the 3D algorithms shown above to get me started on working some algorithm out myself.
c) anybody who has a cousin who has been working on a 4D Constructive solid geometry library in his parents' basement and is looking for somebody to share it with.
Edit: jwc845 asked if the 4-polytopes are convex. The answer is yes. That said, there are multiple convex 4-polytopes. The union of a subset of these may not be convex.
Edit: Apparently there were some mistakes on my part with terminology. I was using polychrons and polychron. The correct spelling is polychoron and polychora. Furthermore, there was some confusion about this term so I have largely replaced it with 4-polytope in the text. Thanks to Dr. Richard Klitzing for his help in the comments.