Donald Bren School of Information and Computer Sciences
Speed-ups in constructive solid geometry
- Author(s): Eppstein, David
- et al.
We convert constructive solid geometry input to explicit representations of polygons, polyhedra, or more generally d-dimensional polyhedra, in time O(n^d), improving a previous O(n^d log n) bound. We then show that any Boolean formula can be preprocessed in time O(n log n/ log log n) so that the value of the formula can be maintained, as variables are changed one by one, in time O(log n/ log log n) per change; this speeds up certain output-sensitive algorithms for constructive solid geometry.