maintaining center of mass of multidimensional integer box with some "orthants" removed

I'm interested in efficiently keeping track of the center of mass of a large box on the integer lattice from which orthant-shaped regions are repeatedly carved out. I've been poking around in the computational geometry literature, and there's a variety of data structures that might be relevant, but most of the discussion is about visibility computations (for computer graphics) or nearest neighbor finding (for data mining and such).

The paper http://www.graphicsinterface.org/pre1996/92-NaylorSolidGeometry.pdf, i.e.:

Naylor, Bruce F.  Interactive Solid Geometry via Partitioning Trees, 
        Proc. Graphics Inte开发者_运维百科rface '92, 1992, pp 11-18. 

discusses a system that represents geometric objects by "binary space partitioning trees", supports set operations, and has an intriguing mention (without details) that the center of mass of objects is recomputed after set operations. Perhaps I have a blind spot, but it's not immediately apparent to me how to efficiently update the center of mass during the tree merging algorithm, and I haven't found a discussion of center of mass computations in papers that cite the Naylor one. Any pointers?

---

A k-d tree is quite literally what you're looking for here seeing as your cuts are inherently axis-aligned but at arbitrary positions. Dealing with generalizations such as binary space partitioning schemes as mentioned in the paper sounds like a layer of complexity that you don't need and will reduce performance.

With a k-d tree you'll be able to calculate and remove intersections with large regions disappearing. If you store the weight and center of mass for each k-d tree node's region within node itself you ought to be able to erase its contribution to the total center of mass without needing to consider child nodes.

By doing this, effectively you'll be building a tree of volumes represented as point masses. Each node can be calculated from its children as needed.