Cutting hyperplanes for divide-and-conquer

Research output: Contribution to journalArticle

179 Scopus citations

Abstract

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
Volume9
Issue number1
DOIs
StatePublished - Dec 1 1993

All Science Journal Classification (ASJC) codes

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

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

  • Cite this