Given n hyperplanes in Ed, a (1/r)-cutting is a collection of simplices with disjoint interiors, which together cover Ed 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(rd) size in O(nrd-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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics