Asymptotic speed-ups in constructive solid geometry.
D. Eppstein.
Tech. Rep. 92-87, ICS, UCI, 1992.
Algorithmica 13: 462–471, 1995.
Finds boundary representations of CSG objects. Uses techniques from dynamic graph algorithms, including a tree partitioning technique of Frederickson and a new data structure for maintaining the value of a Boolean expression with changing variables in time O(log n / log log n) per update.