Skip to main content
Open Access Publications from the University of California

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.

Main Content
Current View