Asymptotic speed-ups in constructive solid geometry.
D. Eppstein.
Tech. Rep. 92-87, ICS, UCI, 1992.
Algorithmica 13: 462–471, 1995,
doi:10.1007/BF01190849.
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.