Before revision:  Given a set of n input  curves and a positive integer D, we efficiently construct a decomposition of space into O(D^3\log^3{D}) open cells, each of which meets O(n/D^2) curves from the input.
After revision:  Given a set of n input curves and a positive integer D, we efficiently construct a decomposition of space into O(D^3\log^3{D}) open "cells," each of which meets O(n/D^2) curves from the input.