Cutting hyperplanes for divide-and-conquer

Given n hyperplanes in E^d, a (1/r)-cutting is a collection of simplices with disjoint interiors, which together cover E^d and such that the interior of each simplex intersects at most n/r hyperplanes. We present a deterministic algorithm for computing a (1/r)-cutting of O(r^d) size in O(nr^d-1) time. If we require the incidences between the hyperplanes and the simplices of the cutting to be provided, then the algorithm is optimal. Our method is based on a hierarchical construction of cuttings, which also provides a simple optimal data structure for locating a point in an arrangement of hyperplanes. We mention several other applications of our result, e.g., counting segment intersections, Hopcroft's line/point incidence problem, linear programming in fixed dimension.