Cutting hyperplanes for divide-and-conquer

Research output: Contribution to journalArticlepeer-review

218 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)145-158
Number of pages14
JournalDiscrete & Computational Geometry
Issue number1
StatePublished - Dec 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Cutting hyperplanes for divide-and-conquer'. Together they form a unique fingerprint.

Cite this